From a88280d67fcf4ce49728c452bd7353ada2afb8c7 Mon Sep 17 00:00:00 2001 From: khizmax Date: Fri, 25 Mar 2016 00:04:19 +0300 Subject: [PATCH] Migrated CuckooSet unit tests to gtest --- projects/Win/vc14/gtest-striped-set.vcxproj | 15 + .../vc14/gtest-striped-set.vcxproj.filters | 6 + test/unit/striped-set/CMakeLists.txt | 1 + test/unit/striped-set/cuckoo_set.cpp | 517 +++++++++++++++++ test/unit/striped-set/test_intrusive_set.h | 6 +- test/unit/striped-set/test_set.h | 527 ++++++++++++++++++ 6 files changed, 1069 insertions(+), 3 deletions(-) create mode 100644 test/unit/striped-set/cuckoo_set.cpp create mode 100644 test/unit/striped-set/test_set.h diff --git a/projects/Win/vc14/gtest-striped-set.vcxproj b/projects/Win/vc14/gtest-striped-set.vcxproj index 482b02e8..4175bbbd 100644 --- a/projects/Win/vc14/gtest-striped-set.vcxproj +++ b/projects/Win/vc14/gtest-striped-set.vcxproj @@ -28,6 +28,20 @@ + + 4503 + 4503 + 4503 + 4503 + 4503 + 4503 + _SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) + @@ -48,6 +62,7 @@ + {648021D3-6E18-4B94-88B8-F6A59609E210} diff --git a/projects/Win/vc14/gtest-striped-set.vcxproj.filters b/projects/Win/vc14/gtest-striped-set.vcxproj.filters index dd452fec..a8e171dc 100644 --- a/projects/Win/vc14/gtest-striped-set.vcxproj.filters +++ b/projects/Win/vc14/gtest-striped-set.vcxproj.filters @@ -45,6 +45,9 @@ Source Files + + Source Files + @@ -53,5 +56,8 @@ Header Files + + Header Files + \ No newline at end of file diff --git a/test/unit/striped-set/CMakeLists.txt b/test/unit/striped-set/CMakeLists.txt index 968c32d7..e4229aef 100644 --- a/test/unit/striped-set/CMakeLists.txt +++ b/test/unit/striped-set/CMakeLists.txt @@ -4,6 +4,7 @@ set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wno-invalid-offsetof -DCDSUNIT_ENABLE_B set(CDSGTEST_SET_SOURCES ../main.cpp + cuckoo_set.cpp intrusive_boost_avl_set.cpp intrusive_boost_list.cpp intrusive_boost_set.cpp diff --git a/test/unit/striped-set/cuckoo_set.cpp b/test/unit/striped-set/cuckoo_set.cpp new file mode 100644 index 00000000..a01f2d61 --- /dev/null +++ b/test/unit/striped-set/cuckoo_set.cpp @@ -0,0 +1,517 @@ +/* + 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_set.h" + +#include + +namespace { + namespace cc = cds::container; + + class CuckooSet : public cds_test::container_set + { + protected: + typedef cds_test::container_set base_class; + + template + void test( Set& s ) + { + // Precondition: set is empty + // Postcondition: set is empty + + base_class::test_< Set::c_isSorted>( s ); + } + + //void SetUp() + //{} + + //void TearDown() + //{} + }; + + struct store_hash_traits: public cc::cuckoo::traits + { + static bool const store_hash = true; + }; + + +//************************************************************ +// striped set + + TEST_F( CuckooSet, striped_list_unordered ) + { + struct set_traits: public cc::cuckoo::traits + { + typedef cds::opt::hash_tuple< hash1, hash2 > hash; + typedef base_class::equal_to equal_to; + typedef cc::cuckoo::list probeset_type; + }; + typedef cc::CuckooSet< int_item, set_traits > set_type; + + set_type s; + test( s ); + } + + TEST_F( CuckooSet, striped_vector_unordered ) + { + struct set_traits: public cc::cuckoo::traits + { + typedef cds::opt::hash_tuple< hash1, hash2 > hash; + typedef base_class::equal_to equal_to; + typedef cc::cuckoo::vector<4> probeset_type; + }; + typedef cc::CuckooSet< int_item, set_traits > set_type; + + set_type s( 32, 4 ); + test( s ); + } + + TEST_F( CuckooSet, striped_list_ordered_cmp ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::compare< cmp > + ,cc::cuckoo::probeset_type< cc::cuckoo::list > + >::type + > set_type; + + set_type s( 32, 6, 4 ); + test( s ); + } + + TEST_F( CuckooSet, striped_vector_ordered_cmp ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::compare< cmp > + ,cc::cuckoo::probeset_type< cc::cuckoo::vector<8>> + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( ht ); + test( s ); + } + + TEST_F( CuckooSet, striped_list_ordered_less ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::less< less > + ,cc::cuckoo::probeset_type< cc::cuckoo::list > + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( 32, 6, 4, ht ); + test( s ); + } + + TEST_F( CuckooSet, striped_vector_ordered_less ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::less< less > + ,cc::cuckoo::probeset_type< cc::cuckoo::vector<6>> + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( std::move( ht ) ); + test( s ); + } + + TEST_F( CuckooSet, striped_list_ordered_cmpmix ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::less< less > + ,cds::opt::compare< cmp > + ,cc::cuckoo::probeset_type< cc::cuckoo::list > + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( 32, 6, 0, std::move( ht ) ); + test( s ); + } + + TEST_F( CuckooSet, striped_vector_ordered_cmpmix ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::less< less > + ,cds::opt::compare< cmp > + ,cc::cuckoo::probeset_type< cc::cuckoo::vector<6>> + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( std::move( ht ) ); + test( s ); + } + + TEST_F( CuckooSet, striped_list_ordered_stat ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::less< less > + ,cds::opt::compare< cmp > + ,cds::opt::stat< cc::cuckoo::stat > + ,cc::cuckoo::probeset_type< cc::cuckoo::list > + >::type + > set_type; + + set_type s; + test( s ); + } + + TEST_F( CuckooSet, striped_vector_ordered_stat ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::less< less > + ,cds::opt::compare< cmp > + ,cds::opt::stat< cc::cuckoo::stat > + ,cc::cuckoo::probeset_type< cc::cuckoo::vector<8>> + >::type + > set_type; + + set_type s; + test( s ); + } + + TEST_F( CuckooSet, striped_list_unordered_storehash ) + { + struct set_traits: public store_hash_traits + { + typedef cds::opt::hash_tuple< hash1, hash2 > hash; + typedef base_class::equal_to equal_to; + typedef cc::cuckoo::list probeset_type; + typedef cc::cuckoo::stat stat; + }; + typedef cc::CuckooSet< int_item, set_traits > set_type; + + set_type s; + test( s ); + } + + TEST_F( CuckooSet, striped_vector_unordered_storehash ) + { + struct set_traits: public store_hash_traits + { + typedef cds::opt::hash_tuple< hash1, hash2 > hash; + typedef base_class::equal_to equal_to; + typedef cc::cuckoo::stat stat; + typedef cc::cuckoo::vector<4> probeset_type; + }; + typedef cc::CuckooSet< int_item, set_traits > set_type; + + set_type s( 32, 4 ); + test( s ); + } + + TEST_F( CuckooSet, striped_list_ordered_storehash ) + { + typedef cc::CuckooSet< int_item + ,cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::less< less > + ,cds::opt::compare< cmp > + ,cc::cuckoo::probeset_type< cc::cuckoo::list > + ,cc::cuckoo::store_hash< true > + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( 32, 6, 0, std::move( ht )); + test( s ); + } + + TEST_F( CuckooSet, striped_vector_ordered_storehash ) + { + typedef cc::CuckooSet< int_item + ,cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::less< less > + ,cds::opt::compare< cmp > + ,cc::cuckoo::probeset_type< cc::cuckoo::vector<6>> + ,cc::cuckoo::store_hash< true > + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( std::move( ht )); + test( s ); + } + + +//************************************************************ +// refinable set + + TEST_F( CuckooSet, refinable_list_unordered ) + { + struct set_traits: public cc::cuckoo::traits + { + typedef cds::opt::hash_tuple< hash1, hash2 > hash; + typedef base_class::equal_to equal_to; + typedef cc::cuckoo::list probeset_type; + typedef cc::cuckoo::refinable<> mutex_policy; + }; + typedef cc::CuckooSet< int_item, set_traits > set_type; + + set_type s; + test( s ); + } + + TEST_F( CuckooSet, refinable_vector_unordered ) + { + struct set_traits: public cc::cuckoo::traits + { + typedef cc::cuckoo::refinable<> mutex_policy; + typedef cds::opt::hash_tuple< hash1, hash2 > hash; + typedef base_class::equal_to equal_to; + typedef cc::cuckoo::vector<4> probeset_type; + }; + typedef cc::CuckooSet< int_item, set_traits > set_type; + + set_type s( 32, 4 ); + test( s ); + } + + TEST_F( CuckooSet, refinable_list_ordered_cmp ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::mutex_policy< cc::cuckoo::refinable<>> + ,cds::opt::compare< cmp > + ,cc::cuckoo::probeset_type< cc::cuckoo::list > + >::type + > set_type; + + set_type s( 32, 6, 4 ); + test( s ); + } + + TEST_F( CuckooSet, refinable_vector_ordered_cmp ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 >> + ,cds::opt::mutex_policy< cc::cuckoo::refinable<>> + ,cds::opt::compare< cmp > + ,cc::cuckoo::probeset_type< cc::cuckoo::vector<8>> + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( ht ); + test( s ); + } + + TEST_F( CuckooSet, refinable_list_ordered_less ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::mutex_policy< cc::cuckoo::refinable<>> + ,cds::opt::less< less > + ,cc::cuckoo::probeset_type< cc::cuckoo::list > + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( 32, 6, 4, ht ); + test( s ); + } + + TEST_F( CuckooSet, refinable_vector_ordered_less ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::mutex_policy< cc::cuckoo::refinable<>> + ,cds::opt::less< less > + ,cc::cuckoo::probeset_type< cc::cuckoo::vector<6>> + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( std::move( ht ) ); + test( s ); + } + + TEST_F( CuckooSet, refinable_list_ordered_cmpmix ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::mutex_policy< cc::cuckoo::refinable<>> + ,cds::opt::less< less > + ,cds::opt::compare< cmp > + ,cc::cuckoo::probeset_type< cc::cuckoo::list > + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( 32, 6, 0, std::move( ht ) ); + test( s ); + } + + TEST_F( CuckooSet, refinable_vector_ordered_cmpmix ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::mutex_policy< cc::cuckoo::refinable<>> + ,cds::opt::less< less > + ,cds::opt::compare< cmp > + ,cc::cuckoo::probeset_type< cc::cuckoo::vector<6>> + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( std::move( ht ) ); + test( s ); + } + + TEST_F( CuckooSet, refinable_list_ordered_stat ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::mutex_policy< cc::cuckoo::refinable<>> + ,cds::opt::less< less > + ,cds::opt::compare< cmp > + ,cds::opt::stat< cc::cuckoo::stat > + ,cc::cuckoo::probeset_type< cc::cuckoo::list > + >::type + > set_type; + + set_type s; + test( s ); + } + + TEST_F( CuckooSet, refinable_vector_ordered_stat ) + { + typedef cc::CuckooSet< int_item + , cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::mutex_policy< cc::cuckoo::refinable<>> + ,cds::opt::less< less > + ,cds::opt::compare< cmp > + ,cds::opt::stat< cc::cuckoo::stat > + ,cc::cuckoo::probeset_type< cc::cuckoo::vector<8>> + >::type + > set_type; + + set_type s; + test( s ); + } + + TEST_F( CuckooSet, refinable_list_unordered_storehash ) + { + struct set_traits: public store_hash_traits + { + typedef cc::cuckoo::refinable<> mutex_policy; + typedef cds::opt::hash_tuple< hash1, hash2 > hash; + typedef base_class::equal_to equal_to; + typedef cc::cuckoo::list probeset_type; + typedef cc::cuckoo::stat stat; + }; + typedef cc::CuckooSet< int_item, set_traits > set_type; + + set_type s; + test( s ); + } + + TEST_F( CuckooSet, refinable_vector_unordered_storehash ) + { + struct set_traits: public store_hash_traits + { + typedef cds::opt::hash_tuple< hash1, hash2 > hash; + typedef cc::cuckoo::refinable<> mutex_policy; + typedef base_class::equal_to equal_to; + typedef cc::cuckoo::stat stat; + typedef cc::cuckoo::vector<4> probeset_type; + }; + typedef cc::CuckooSet< int_item, set_traits > set_type; + + set_type s( 32, 4 ); + test( s ); + } + + TEST_F( CuckooSet, refinable_list_ordered_storehash ) + { + typedef cc::CuckooSet< int_item + ,cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::mutex_policy< cc::cuckoo::refinable<>> + ,cds::opt::less< less > + ,cds::opt::compare< cmp > + ,cc::cuckoo::probeset_type< cc::cuckoo::list > + ,cc::cuckoo::store_hash< true > + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( 32, 6, 0, std::move( ht )); + test( s ); + } + + TEST_F( CuckooSet, refinable_vector_ordered_storehash ) + { + typedef cc::CuckooSet< int_item + ,cc::cuckoo::make_traits< + cds::opt::hash< std::tuple< hash1, hash2 > > + ,cds::opt::mutex_policy< cc::cuckoo::refinable<>> + ,cds::opt::less< less > + ,cds::opt::compare< cmp > + ,cc::cuckoo::probeset_type< cc::cuckoo::vector<6>> + ,cc::cuckoo::store_hash< true > + >::type + > set_type; + + typename set_type::hash_tuple_type ht; + set_type s( std::move( ht )); + test( s ); + } + + +} // namespace diff --git a/test/unit/striped-set/test_intrusive_set.h b/test/unit/striped-set/test_intrusive_set.h index 6776f456..0e6acfab 100644 --- a/test/unit/striped-set/test_intrusive_set.h +++ b/test/unit/striped-set/test_intrusive_set.h @@ -28,8 +28,8 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ -#ifndef CDSUNIT_SET_TEST_INTRUSIVE_SET_H -#define CDSUNIT_SET_TEST_INTRUSIVE_SET_H +#ifndef CDSUNIT_STRIPED_SET_TEST_INTRUSIVE_SET_H +#define CDSUNIT_STRIPED_SET_TEST_INTRUSIVE_SET_H #include #include @@ -506,4 +506,4 @@ namespace cds_test { } // namespace cds_test -#endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SET_H +#endif // #ifndef CDSUNIT_STRIPED_SET_TEST_INTRUSIVE_SET_H diff --git a/test/unit/striped-set/test_set.h b/test/unit/striped-set/test_set.h new file mode 100644 index 00000000..a678b90e --- /dev/null +++ b/test/unit/striped-set/test_set.h @@ -0,0 +1,527 @@ +/* + 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_STRIPED_SET_TEST_SET_H +#define CDSUNIT_STRIPED_SET_TEST_SET_H + +#include +#include + +#include +#include // ref + +// forward declaration +namespace cds { namespace container {}} + +namespace cds_test { + namespace co = cds::opt; + + class container_set : public fixture + { + public: + static size_t const kSize = 1000; + + struct stat + { + unsigned int nFindCount; + unsigned int nUpdateNewCount; + unsigned int nUpdateCount; + mutable unsigned int nEraseCount; + + stat() + { + clear_stat(); + } + + void clear_stat() + { + memset( this, 0, sizeof( *this ) ); + } + }; + + struct other_item { + int nKey; + + explicit other_item( int k ) + : nKey( k ) + {} + + int key() const + { + return nKey; + } + }; + + struct int_item: public stat + { + int nKey; + int nVal; + std::string strVal; + + int_item() + : nKey( 0 ) + , nVal( 0 ) + {} + + explicit int_item( int k ) + : nKey( k ) + , nVal( k * 2 ) + {} + + template + explicit int_item( Q const& src ) + : nKey( src.key() ) + , nVal( 0 ) + {} + + int_item( int_item const& src ) + : nKey( src.nKey ) + , nVal( src.nVal ) + , strVal( src.strVal ) + {} + + int_item( int_item&& src ) + : nKey( src.nKey ) + , nVal( src.nVal ) + , strVal( std::move( src.strVal ) ) + {} + + int_item( int k, std::string&& s ) + : nKey( k ) + , nVal( k * 2 ) + , strVal( std::move( s ) ) + {} + + explicit int_item( other_item const& s ) + : nKey( s.key() ) + , nVal( s.key() * 2 ) + {} + + int key() const + { + return nKey; + } + }; + + struct hash1 { + size_t operator()( int i ) const + { + return co::v::hash()(i); + } + template + size_t operator()( const Item& i ) const + { + return (*this)(i.key()); + } + }; + + struct hash2: private hash1 + { + typedef hash1 base_class; + + size_t operator()( int i ) const + { + size_t h = ~(base_class::operator()( i )); + return ~h + 0x9e3779b9 + (h << 6) + (h >> 2); + } + template + size_t operator()( const Item& i ) const + { + size_t h = ~(base_class::operator()( i )); + return ~h + 0x9e3779b9 + (h << 6) + (h >> 2); + } + }; + + struct less + { + bool operator ()( int_item const& v1, int_item const& v2 ) const + { + return v1.key() < v2.key(); + } + + template + bool operator ()( int_item const& v1, const Q& v2 ) const + { + return v1.key() < v2; + } + + template + bool operator ()( const Q& v1, int_item const& v2 ) const + { + return v1 < v2.key(); + } + }; + + struct equal_to + { + bool operator ()( int_item const& v1, int_item const& v2 ) const + { + return v1.key() == v2.key(); + } + + template + bool operator ()( int_item const& v1, const Q& v2 ) const + { + return v1.key() == v2; + } + + template + bool operator ()( const Q& v1, int_item const& v2 ) const + { + return v1 == v2.key(); + } + }; + + struct cmp { + int operator ()( int_item const& v1, int_item const& v2 ) const + { + if ( v1.key() < v2.key() ) + return -1; + return v1.key() > v2.key() ? 1 : 0; + } + + template + int operator ()( T const& v1, int v2 ) const + { + if ( v1.key() < v2 ) + return -1; + return v1.key() > v2 ? 1 : 0; + } + + template + int operator ()( int v1, T const& v2 ) const + { + if ( v1 < v2.key() ) + return -1; + return v1 > v2.key() ? 1 : 0; + } + }; + + struct other_less { + template + bool operator()( Q const& lhs, T const& rhs ) const + { + return lhs.key() < rhs.key(); + } + }; + + struct other_equal_to { + template + bool operator()( Q const& lhs, T const& rhs ) const + { + return lhs.key() == rhs.key(); + } + }; + + protected: + template + void test( Set& s ) + { + test_< true >( s ); + } + + template + void test_( Set& s ) + { + // Precondition: set is empty + // Postcondition: set is empty + + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + size_t const nSetSize = kSize; + + typedef typename Set::value_type value_type; + typedef typename std::conditional< Sorted, other_less, other_equal_to >::type other_predicate; + + 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() ); + + // insert/find + for ( auto idx : indices ) { + auto& i = data[idx]; + + ASSERT_FALSE( s.contains( i.nKey ) ); + ASSERT_FALSE( s.contains( i ) ); + ASSERT_FALSE( s.contains( other_item( i.key() ), other_predicate())); + ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} )); + ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} )); + ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} )); + + std::pair updResult; + + std::string str; + updResult = s.update( i.key(), []( bool bNew, value_type&, int ) + { + ASSERT_TRUE( false ); + }, false ); + EXPECT_FALSE( updResult.first ); + EXPECT_FALSE( updResult.second ); + + switch ( idx % 8 ) { + case 0: + ASSERT_TRUE( s.insert( i )); + ASSERT_FALSE( s.insert( i )); + updResult = s.update( i, []( bool bNew, value_type& val, value_type const& arg) + { + EXPECT_FALSE( bNew ); + EXPECT_EQ( val.key(), arg.key() ); + }, false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + break; + case 1: + ASSERT_TRUE( s.insert( i.key() )); + ASSERT_FALSE( s.insert( i.key() )); + updResult = s.update( i.key(), []( bool bNew, value_type& val, int arg) + { + EXPECT_FALSE( bNew ); + EXPECT_EQ( val.key(), arg ); + }, false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + break; + case 2: + ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } )); + ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } )); + ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key ) + { + EXPECT_EQ( v.key(), key ); + EXPECT_EQ( v.nFindCount, 1 ); + })); + break; + case 3: + ASSERT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } )); + ASSERT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } )); + ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key ) + { + EXPECT_EQ( v.key(), key ); + EXPECT_EQ( v.nFindCount, 1 ); + })); + break; + case 4: + updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg ) + { + EXPECT_TRUE( bNew ); + EXPECT_EQ( v.key(), arg.key() ); + ++v.nUpdateNewCount; + }); + EXPECT_TRUE( updResult.first ); + EXPECT_TRUE( updResult.second ); + + updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg ) + { + EXPECT_FALSE( bNew ); + EXPECT_EQ( v.key(), arg.key() ); + ++v.nUpdateNewCount; + }, false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + + ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key ) + { + EXPECT_EQ( v.key(), key ); + EXPECT_EQ( v.nUpdateNewCount, 2 ); + })); + break; + case 5: + updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg ) + { + EXPECT_TRUE( bNew ); + EXPECT_EQ( v.key(), arg ); + ++v.nUpdateNewCount; + }); + EXPECT_TRUE( updResult.first ); + EXPECT_TRUE( updResult.second ); + + updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg ) + { + EXPECT_FALSE( bNew ); + EXPECT_EQ( v.key(), arg ); + ++v.nUpdateNewCount; + }, false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + + ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg ) + { + EXPECT_EQ( v.key(), arg.key() ); + EXPECT_EQ( v.nUpdateNewCount, 2 ); + })); + break; + case 6: + ASSERT_TRUE( s.emplace( i.key())); + ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg ) + { + EXPECT_EQ( v.key(), arg.key() ); + EXPECT_EQ( v.nVal, arg.nVal ); + })); + break; + case 7: + str = "Hello!"; + ASSERT_TRUE( s.emplace( i.key(), std::move( str ))); + EXPECT_TRUE( str.empty()); + ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg ) + { + EXPECT_EQ( v.key(), arg.key() ); + EXPECT_EQ( v.nVal, arg.nVal ); + EXPECT_EQ( v.strVal, std::string( "Hello!" )); + } ) ); + break; + default: + // forgot anything?.. + ASSERT_TRUE( false ); + } + + ASSERT_TRUE( s.contains( i.nKey ) ); + ASSERT_TRUE( s.contains( i ) ); + ASSERT_TRUE( s.contains( other_item( i.key() ), other_predicate() ) ); + ASSERT_TRUE( s.find( i.nKey, []( value_type&, int ) {} ) ); + ASSERT_TRUE( s.find( i, []( value_type&, value_type const& ) {} ) ); + ASSERT_TRUE( s.find_with( other_item( i.key() ), other_predicate(), []( value_type&, other_item const& ) {} ) ); + } + + ASSERT_FALSE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, nSetSize ); + + // erase + shuffle( indices.begin(), indices.end() ); + for ( auto idx : indices ) { + auto& i = data[idx]; + + ASSERT_TRUE( s.contains( i.nKey ) ); + ASSERT_TRUE( s.contains( i ) ); + ASSERT_TRUE( s.contains( other_item( i.key() ), other_predicate() ) ); + ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) + { + v.nFindCount = 1; + })); + ASSERT_TRUE( s.find( i, []( value_type& v, value_type const& ) + { + EXPECT_EQ( ++v.nFindCount, 2 ); + })); + ASSERT_TRUE( s.find_with( other_item( i.key() ), other_predicate(), []( value_type& v, other_item const& ) + { + EXPECT_EQ( ++v.nFindCount, 3 ); + })); + + int nKey = i.key() - 1; + switch ( idx % 6 ) { + case 0: + ASSERT_TRUE( s.erase( i.key())); + ASSERT_FALSE( s.erase( i.key())); + break; + case 1: + ASSERT_TRUE( s.erase( i )); + ASSERT_FALSE( s.erase( i )); + break; + case 2: + ASSERT_TRUE( s.erase_with( other_item( i.key()), other_predicate())); + ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_predicate() ) ); + break; + case 3: + ASSERT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey ); + + nKey = i.key() - 1; + ASSERT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey + 1 ); + break; + case 4: + ASSERT_TRUE( s.erase( i, [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey ); + + nKey = i.key() - 1; + ASSERT_FALSE( s.erase( i, [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey + 1 ); + break; + case 5: + ASSERT_TRUE( s.erase_with( other_item( i.key()), other_predicate(), [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey ); + + nKey = i.key() - 1; + ASSERT_FALSE( s.erase_with( other_item( i.key()), other_predicate(), [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey + 1 ); + break; + } + + ASSERT_FALSE( s.contains( i.nKey ) ); + ASSERT_FALSE( s.contains( i ) ); + ASSERT_FALSE( s.contains( other_item( i.key() ), other_predicate())); + ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} )); + ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} )); + ASSERT_FALSE( s.find_with( other_item( i.key()), other_predicate(), []( value_type&, other_item const& ) {} )); + } + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + + + // clear + for ( auto& i : data ) { + ASSERT_TRUE( s.insert( i ) ); + } + + ASSERT_FALSE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, nSetSize ); + + s.clear(); + + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + } + }; + +} // namespace cds_test + +#endif // CDSUNIT_STRIPED_SET_TEST_SET_H -- 2.34.1