From 351cd0b13d6b0c44122b9f404dbf97507c1d9724 Mon Sep 17 00:00:00 2001 From: khizmax Date: Fri, 27 Mar 2015 12:29:58 +0300 Subject: [PATCH] Splitted up set_delodd test Renamed set_insdel_func files --- projects/Win/vc12/unit-set-delodd.vcxproj | 28 +- projects/Win/vc12/unit-set-insdel.vcxproj | 32 +- .../Win/vc12/unit-set-insdel.vcxproj.filters | 12 +- projects/source.unit.set.mk | 19 +- tests/unit/map2/map_delodd.cpp | 2 +- tests/unit/set2/set_delodd.cpp | 810 +----------------- tests/unit/set2/set_delodd.h | 752 ++++++++++++++++ tests/unit/set2/set_delodd_cuckoo.cpp | 10 + tests/unit/set2/set_delodd_ellentree.cpp | 10 + tests/unit/set2/set_delodd_michael.cpp | 10 + tests/unit/set2/set_delodd_skip.cpp | 10 + tests/unit/set2/set_delodd_split.cpp | 10 + ...l_func6.cpp => set_insdel_func_cuckoo.cpp} | 0 ...unc7.cpp => set_insdel_func_ellentree.cpp} | 0 ...unc5.cpp => set_insdel_func_refinable.cpp} | 0 ...del_func3.cpp => set_insdel_func_skip.cpp} | 0 ...el_func2.cpp => set_insdel_func_split.cpp} | 0 ..._func4.cpp => set_insdel_func_striped.cpp} | 0 tests/unit/set2/set_types.h | 14 + 19 files changed, 904 insertions(+), 815 deletions(-) create mode 100644 tests/unit/set2/set_delodd.h create mode 100644 tests/unit/set2/set_delodd_cuckoo.cpp create mode 100644 tests/unit/set2/set_delodd_ellentree.cpp create mode 100644 tests/unit/set2/set_delodd_michael.cpp create mode 100644 tests/unit/set2/set_delodd_skip.cpp create mode 100644 tests/unit/set2/set_delodd_split.cpp rename tests/unit/set2/{set_insdel_func6.cpp => set_insdel_func_cuckoo.cpp} (100%) rename tests/unit/set2/{set_insdel_func7.cpp => set_insdel_func_ellentree.cpp} (100%) rename tests/unit/set2/{set_insdel_func5.cpp => set_insdel_func_refinable.cpp} (100%) rename tests/unit/set2/{set_insdel_func3.cpp => set_insdel_func_skip.cpp} (100%) rename tests/unit/set2/{set_insdel_func2.cpp => set_insdel_func_split.cpp} (100%) rename tests/unit/set2/{set_insdel_func4.cpp => set_insdel_func_striped.cpp} (100%) diff --git a/projects/Win/vc12/unit-set-delodd.vcxproj b/projects/Win/vc12/unit-set-delodd.vcxproj index 09ee4df8..ada62c81 100644 --- a/projects/Win/vc12/unit-set-delodd.vcxproj +++ b/projects/Win/vc12/unit-set-delodd.vcxproj @@ -44,6 +44,14 @@ + + + + + + + + {AF7B2253-2E6D-4992-94D9-4B3699C54929} @@ -214,7 +222,7 @@ /bigobj /Zc:inline %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -238,7 +246,7 @@ /bigobj %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -262,7 +270,7 @@ /bigobj /Zc:inline %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - CDS_USE_VLD;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;CDS_USE_VLD;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -289,7 +297,7 @@ /bigobj /Zc:inline %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -316,7 +324,7 @@ /bigobj %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -343,7 +351,7 @@ /bigobj /Zc:inline %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - CDS_USE_VLD;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;CDS_USE_VLD;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -370,7 +378,7 @@ true Speed $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) MultiThreadedDLL true @@ -398,7 +406,7 @@ true Speed $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) MultiThreadedDLL true @@ -430,7 +438,7 @@ true Speed $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) MultiThreadedDLL true @@ -461,7 +469,7 @@ true Speed $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) MultiThreadedDLL true diff --git a/projects/Win/vc12/unit-set-insdel.vcxproj b/projects/Win/vc12/unit-set-insdel.vcxproj index 78c9695a..c6797fb3 100644 --- a/projects/Win/vc12/unit-set-insdel.vcxproj +++ b/projects/Win/vc12/unit-set-insdel.vcxproj @@ -45,12 +45,12 @@ - - - - - - + + + + + + @@ -225,7 +225,7 @@ /bigobj /Zc:inline %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -249,7 +249,7 @@ /bigobj %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -273,7 +273,7 @@ /bigobj /Zc:inline %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - CDS_USE_VLD;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;CDS_USE_VLD;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -300,7 +300,7 @@ /bigobj /Zc:inline %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -327,7 +327,7 @@ /bigobj %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -354,7 +354,7 @@ /bigobj /Zc:inline %(AdditionalOptions) Disabled $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - CDS_USE_VLD;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;CDS_USE_VLD;WIN32;_DEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) true EnableFastChecks MultiThreadedDebugDLL @@ -381,7 +381,7 @@ true Speed $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) MultiThreadedDLL true @@ -409,7 +409,7 @@ true Speed $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) MultiThreadedDLL true @@ -441,7 +441,7 @@ true Speed $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) MultiThreadedDLL true @@ -472,7 +472,7 @@ true Speed $(SolutionDir)..\..\..;$(SolutionDir)..\..\..\tests\unit;$(SolutionDir)..\..\..\tests;$(BOOST_PATH);%(AdditionalIncludeDirectories) - WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) + _SCL_SECURE_NO_WARNINGS;WIN32;NDEBUG;_CONSOLE;_WIN32_WINNT=0x0501;_SCL_SECURE=0;%(PreprocessorDefinitions) MultiThreadedDLL true diff --git a/projects/Win/vc12/unit-set-insdel.vcxproj.filters b/projects/Win/vc12/unit-set-insdel.vcxproj.filters index 476f031c..7701251b 100644 --- a/projects/Win/vc12/unit-set-insdel.vcxproj.filters +++ b/projects/Win/vc12/unit-set-insdel.vcxproj.filters @@ -6,22 +6,22 @@ set_insdel_func - + set_insdel_func - + set_insdel_func - + set_insdel_func - + set_insdel_func - + set_insdel_func - + set_insdel_func diff --git a/projects/source.unit.set.mk b/projects/source.unit.set.mk index 8fd0dd51..03fcb7ec 100644 --- a/projects/source.unit.set.mk +++ b/projects/source.unit.set.mk @@ -1,12 +1,17 @@ CDSUNIT_SET_SOURCES := \ tests/unit/set2/set_insdel_func.cpp \ - tests/unit/set2/set_insdel_func2.cpp \ - tests/unit/set2/set_insdel_func3.cpp \ - tests/unit/set2/set_insdel_func4.cpp \ - tests/unit/set2/set_insdel_func5.cpp \ - tests/unit/set2/set_insdel_func6.cpp \ - tests/unit/set2/set_insdel_func7.cpp \ + tests/unit/set2/set_insdel_func_cuckoo.cpp \ + tests/unit/set2/set_insdel_func_ellentree.cpp \ + tests/unit/set2/set_insdel_func_refinable.cpp \ + tests/unit/set2/set_insdel_func_skip.cpp \ + tests/unit/set2/set_insdel_func_split.cpp \ + tests/unit/set2/set_insdel_func_striped.cpp \ tests/unit/set2/set_insdel_string.cpp \ tests/unit/set2/set_insdelfind.cpp \ - tests/unit/set2/set_delodd.cpp + tests/unit/set2/set_delodd.cpp \ + tests/unit/set2/set_delodd_cuckoo.cpp \ + tests/unit/set2/set_delodd_michael.cpp \ + tests/unit/set2/set_delodd_ellentree.cpp \ + tests/unit/set2/set_delodd_skip.cpp \ + tests/unit/set2/set_delodd_split.cpp \ diff --git a/tests/unit/map2/map_delodd.cpp b/tests/unit/map2/map_delodd.cpp index b2e974f4..c65467ab 100644 --- a/tests/unit/map2/map_delodd.cpp +++ b/tests/unit/map2/map_delodd.cpp @@ -35,7 +35,7 @@ namespace map2 { void Map_DelOdd::myRun(const char *in_name, bool invert /*= false*/) { - setUpParams( m_Cfg.get( "Map_InsDel_func" )); + setUpParams( m_Cfg.get( "Map_DelOdd" )); run_MichaelMap(in_name, invert); run_SplitList(in_name, invert); diff --git a/tests/unit/set2/set_delodd.cpp b/tests/unit/set2/set_delodd.cpp index dc2b56ad..ca033331 100644 --- a/tests/unit/set2/set_delodd.cpp +++ b/tests/unit/set2/set_delodd.cpp @@ -1,789 +1,49 @@ //$$CDS-header$$ -#include "cppunit/thread.h" -#include "set2/set_types.h" -#include // random_shuffle +#include "set2/set_delodd.h" namespace set2 { + CPPUNIT_TEST_SUITE_REGISTRATION( Set_DelOdd ); -# define TEST_SET(X) void X() { test::X >() ; } -# define TEST_SET_EXTRACT(X) void X() { test_extract::X >() ; } -# define TEST_SET_NOLF(X) void X() { test_nolf::X >() ; } -# define TEST_SET_NOLF_EXTRACT(X) void X() { test_nolf_extract::X >() ; } - - namespace { - static size_t c_nSetSize = 1000000 ; // max set size - static size_t c_nInsThreadCount = 4 ; // insert thread count - static size_t c_nDelThreadCount = 4 ; // delete thread count - static size_t c_nExtractThreadCount = 4 ; // extract thread count - static size_t c_nMaxLoadFactor = 8 ; // maximum load factor - static bool c_bPrintGCState = true; - } - - namespace { - struct key_thread - { - size_t nKey; - size_t nThread; - - key_thread( size_t key, size_t threadNo ) - : nKey( key ) - , nThread( threadNo ) - {} - - key_thread() - {} - }; - - typedef SetTypes::key_val key_value_pair; - } - - template <> - struct cmp { - int operator ()(key_thread const& k1, key_thread const& k2) const - { - if ( k1.nKey < k2.nKey ) - return -1; - if ( k1.nKey > k2.nKey ) - return 1; - if ( k1.nThread < k2.nThread ) - return -1; - if ( k1.nThread > k2.nThread ) - return 1; - return 0; - } - int operator ()(key_thread const& k1, size_t k2) const - { - if ( k1.nKey < k2 ) - return -1; - if ( k1.nKey > k2 ) - return 1; - return 0; - } - int operator ()(size_t k1, key_thread const& k2) const - { - if ( k1 < k2.nKey ) - return -1; - if ( k1 > k2.nKey ) - return 1; - return 0; - } - }; - -} // namespace set2 - -namespace std { - template <> - struct less - { - bool operator()(set2::key_thread const& k1, set2::key_thread const& k2) const - { - if ( k1.nKey <= k2.nKey ) - return k1.nKey < k2.nKey || k1.nThread < k2.nThread; - return false; - } - }; - - template <> - struct hash - { - typedef size_t result_type; - typedef set2::key_thread argument_type; - - size_t operator()( set2::key_thread const& k ) const - { - return std::hash()(k.nKey); - } - size_t operator()( size_t k ) const - { - return std::hash()(k); - } - }; - -} // namespace std + size_t Set_DelOdd::c_nSetSize = 1000000; + size_t Set_DelOdd::c_nInsThreadCount; + size_t Set_DelOdd::c_nDelThreadCount; + size_t Set_DelOdd::c_nExtractThreadCount; + size_t Set_DelOdd::c_nMaxLoadFactor; + bool Set_DelOdd::c_bPrintGCState; -namespace boost { - inline size_t hash_value( set2::key_thread const& k ) + void Set_DelOdd::setUpParams( const CppUnitMini::TestCfg& cfg ) { - return std::hash()( k.nKey ); + c_nSetSize = cfg.getSizeT("MapSize", c_nSetSize ); + c_nInsThreadCount = cfg.getSizeT("InsThreadCount", c_nInsThreadCount); + c_nDelThreadCount = cfg.getSizeT("DelThreadCount", c_nDelThreadCount); + c_nExtractThreadCount = cfg.getSizeT("ExtractThreadCount", c_nExtractThreadCount); + c_nMaxLoadFactor = cfg.getSizeT("MaxLoadFactor", c_nMaxLoadFactor); + c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true ); + + if ( c_nInsThreadCount == 0 ) + c_nInsThreadCount = cds::OS::topology::processor_count(); + if ( c_nDelThreadCount == 0 && c_nExtractThreadCount == 0 ) { + c_nExtractThreadCount = cds::OS::topology::processor_count() / 2; + c_nDelThreadCount = cds::OS::topology::processor_count() - c_nExtractThreadCount; + } + + m_arrData.resize( c_nSetSize ); + for ( size_t i = 0; i < c_nSetSize; ++i ) + m_arrData[i] = i; + std::random_shuffle( m_arrData.begin(), m_arrData.end() ); } - template <> - struct hash + void Set_DelOdd::myRun(const char *in_name, bool invert /*= false*/) { - typedef size_t result_type; - typedef set2::key_thread argument_type; + setUpParams( m_Cfg.get( "Map_DelOdd" )); - size_t operator()(set2::key_thread const& k) const - { - return boost::hash()( k.nKey ); - } - size_t operator()(size_t k) const - { - return boost::hash()( k ); - } - }; -} // namespace boost - -namespace set2 { + run_MichaelSet(in_name, invert); + run_SplitList(in_name, invert); + run_SkipListSet(in_name, invert); + run_EllenBinTreeSet(in_name, invert); + run_CuckooSet(in_name, invert); - template - static inline void check_before_clear( Set& /*s*/ ) - {} - - template - static inline void check_before_clear( cds::container::EllenBinTreeSet& s ) - { - CPPUNIT_CHECK_CURRENT( s.check_consistency() ); + endTestCase(); } - - class Set_DelOdd: public CppUnitMini::TestCase - { - std::vector m_arrData; - - protected: - typedef key_thread key_type; - typedef size_t value_type; - - atomics::atomic m_nInsThreadCount; - - // Inserts keys from [0..N) - template - class InsertThread: public CppUnitMini::TestThread - { - Set& m_Set; - - virtual InsertThread * clone() - { - return new InsertThread( *this ); - } - - struct ensure_func - { - template - void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) - {} - }; - public: - size_t m_nInsertSuccess; - size_t m_nInsertFailed; - - public: - InsertThread( CppUnitMini::ThreadPool& pool, Set& rMap ) - : CppUnitMini::TestThread( pool ) - , m_Set( rMap ) - {} - InsertThread( InsertThread& src ) - : CppUnitMini::TestThread( src ) - , m_Set( src.m_Set ) - {} - - Set_DelOdd& getTest() - { - return reinterpret_cast( m_Pool.m_Test ); - } - - virtual void init() { cds::threading::Manager::attachThread() ; } - virtual void fini() { cds::threading::Manager::detachThread() ; } - - virtual void test() - { - Set& rSet = m_Set; - - m_nInsertSuccess = - m_nInsertFailed = 0; - - std::vector& arrData = getTest().m_arrData; - for ( size_t i = 0; i < arrData.size(); ++i ) { - if ( rSet.insert( key_type( arrData[i], m_nThreadNo ))) - ++m_nInsertSuccess; - else - ++m_nInsertFailed; - } - - ensure_func f; - for ( size_t i = arrData.size() - 1; i > 0; --i ) { - if ( arrData[i] & 1 ) { - rSet.ensure( key_type( arrData[i], m_nThreadNo ), f ); - } - } - - getTest().m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release ); - } - }; - - struct key_equal { - bool operator()( key_type const& k1, key_type const& k2 ) const - { - return k1.nKey == k2.nKey; - } - bool operator()( size_t k1, key_type const& k2 ) const - { - return k1 == k2.nKey; - } - bool operator()( key_type const& k1, size_t k2 ) const - { - return k1.nKey == k2; - } - bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const - { - return operator()( k1.key, k2.key ); - } - bool operator ()( key_value_pair const& k1, key_type const& k2 ) const - { - return operator()( k1.key, k2 ); - } - bool operator ()( key_type const& k1, key_value_pair const& k2 ) const - { - return operator()( k1, k2.key ); - } - bool operator ()( key_value_pair const& k1, size_t k2 ) const - { - return operator()( k1.key, k2 ); - } - bool operator ()( size_t k1, key_value_pair const& k2 ) const - { - return operator()( k1, k2.key ); - } - }; - - struct key_less { - bool operator()( key_type const& k1, key_type const& k2 ) const - { - return k1.nKey < k2.nKey; - } - bool operator()( size_t k1, key_type const& k2 ) const - { - return k1 < k2.nKey; - } - bool operator()( key_type const& k1, size_t k2 ) const - { - return k1.nKey < k2; - } - bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const - { - return operator()( k1.key, k2.key ); - } - bool operator ()( key_value_pair const& k1, key_type const& k2 ) const - { - return operator()( k1.key, k2 ); - } - bool operator ()( key_type const& k1, key_value_pair const& k2 ) const - { - return operator()( k1, k2.key ); - } - bool operator ()( key_value_pair const& k1, size_t k2 ) const - { - return operator()( k1.key, k2 ); - } - bool operator ()( size_t k1, key_value_pair const& k2 ) const - { - return operator()( k1, k2.key ); - } - - typedef key_equal equal_to; - }; - - // Deletes odd keys from [0..N) - template - class DeleteThread: public CppUnitMini::TestThread - { - Set& m_Set; - - virtual DeleteThread * clone() - { - return new DeleteThread( *this ); - } - public: - size_t m_nDeleteSuccess; - size_t m_nDeleteFailed; - - public: - DeleteThread( CppUnitMini::ThreadPool& pool, Set& rMap ) - : CppUnitMini::TestThread( pool ) - , m_Set( rMap ) - {} - DeleteThread( DeleteThread& src ) - : CppUnitMini::TestThread( src ) - , m_Set( src.m_Set ) - {} - - Set_DelOdd& getTest() - { - return reinterpret_cast( m_Pool.m_Test ); - } - - virtual void init() { cds::threading::Manager::attachThread() ; } - virtual void fini() { cds::threading::Manager::detachThread() ; } - - virtual void test() - { - Set& rSet = m_Set; - - m_nDeleteSuccess = - m_nDeleteFailed = 0; - - std::vector& arrData = getTest().m_arrData; - if ( m_nThreadNo & 1 ) { - for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { - for ( size_t i = 0; i < arrData.size(); ++i ) { - if ( arrData[i] & 1 ) { - if ( rSet.erase_with( arrData[i], key_less() )) - ++m_nDeleteSuccess; - else - ++m_nDeleteFailed; - } - } - if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) - break; - } - } - else { - for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { - for ( size_t i = arrData.size() - 1; i > 0; --i ) { - if ( arrData[i] & 1 ) { - if ( rSet.erase_with( arrData[i], key_less() )) - ++m_nDeleteSuccess; - else - ++m_nDeleteFailed; - } - } - if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) - break; - } - } - } - }; - - // Extracts odd keys from [0..N) - template - class ExtractThread: public CppUnitMini::TestThread - { - Set& m_Set; - - virtual ExtractThread * clone() - { - return new ExtractThread( *this ); - } - public: - size_t m_nExtractSuccess; - size_t m_nExtractFailed; - - public: - ExtractThread( CppUnitMini::ThreadPool& pool, Set& rMap ) - : CppUnitMini::TestThread( pool ) - , m_Set( rMap ) - {} - ExtractThread( ExtractThread& src ) - : CppUnitMini::TestThread( src ) - , m_Set( src.m_Set ) - {} - - Set_DelOdd& getTest() - { - return reinterpret_cast( m_Pool.m_Test ); - } - - virtual void init() { cds::threading::Manager::attachThread() ; } - virtual void fini() { cds::threading::Manager::detachThread() ; } - - virtual void test() - { - Set& rSet = m_Set; - - m_nExtractSuccess = - m_nExtractFailed = 0; - - typename Set::guarded_ptr gp; - - std::vector& arrData = getTest().m_arrData; - if ( m_nThreadNo & 1 ) { - for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { - for ( size_t i = 0; i < arrData.size(); ++i ) { - if ( arrData[i] & 1 ) { - gp = rSet.extract_with( arrData[i], key_less()); - if ( gp ) - ++m_nExtractSuccess; - else - ++m_nExtractFailed; - gp.release(); - } - } - if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) - break; - } - } - else { - for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { - for ( size_t i = arrData.size() - 1; i > 0; --i ) { - if ( arrData[i] & 1 ) { - gp = rSet.extract_with( arrData[i], key_less()); - if ( gp ) - ++m_nExtractSuccess; - else - ++m_nExtractFailed; - gp.release(); - } - } - if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) - break; - } - } - } - }; - - template - class ExtractThread< cds::urcu::gc, Set >: public CppUnitMini::TestThread - { - Set& m_Set; - - virtual ExtractThread * clone() - { - return new ExtractThread( *this ); - } - public: - size_t m_nExtractSuccess; - size_t m_nExtractFailed; - - public: - ExtractThread( CppUnitMini::ThreadPool& pool, Set& rMap ) - : CppUnitMini::TestThread( pool ) - , m_Set( rMap ) - {} - ExtractThread( ExtractThread& src ) - : CppUnitMini::TestThread( src ) - , m_Set( src.m_Set ) - {} - - Set_DelOdd& getTest() - { - return reinterpret_cast( m_Pool.m_Test ); - } - - virtual void init() { cds::threading::Manager::attachThread() ; } - virtual void fini() { cds::threading::Manager::detachThread() ; } - - virtual void test() - { - Set& rSet = m_Set; - - m_nExtractSuccess = - m_nExtractFailed = 0; - - typename Set::exempt_ptr xp; - - std::vector& arrData = getTest().m_arrData; - if ( m_nThreadNo & 1 ) { - for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { - for ( size_t i = 0; i < arrData.size(); ++i ) { - if ( arrData[i] & 1 ) { - if ( Set::c_bExtractLockExternal ) { - typename Set::rcu_lock l; - xp = rSet.extract_with( arrData[i], key_less() ); - if ( xp ) - ++m_nExtractSuccess; - else - ++m_nExtractFailed; - } - else { - xp = rSet.extract_with( arrData[i], key_less() ); - if ( xp ) - ++m_nExtractSuccess; - else - ++m_nExtractFailed; - } - xp.release(); - } - } - if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) - break; - } - } - else { - for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { - for ( size_t i = arrData.size() - 1; i > 0; --i ) { - if ( arrData[i] & 1 ) { - if ( Set::c_bExtractLockExternal ) { - typename Set::rcu_lock l; - xp = rSet.extract_with( arrData[i], key_less() ); - if ( xp ) - ++m_nExtractSuccess; - else - ++m_nExtractFailed; - } - else { - xp = rSet.extract_with( arrData[i], key_less() ); - if ( xp ) - ++m_nExtractSuccess; - else - ++m_nExtractFailed; - } - xp.release(); - } - } - if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) - break; - } - } - } - }; - - protected: - template - void do_test( size_t nLoadFactor ) - { - Set testSet( c_nSetSize, nLoadFactor ); - do_test_with( testSet ); - analyze( testSet ); - } - - template - void do_test_extract( size_t nLoadFactor ) - { - Set testSet( c_nSetSize, nLoadFactor ); - do_test_extract_with( testSet ); - analyze( testSet ); - } - - template - void do_test_with( Set& testSet ) - { - typedef InsertThread insert_thread; - typedef DeleteThread delete_thread; - - m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release ); - - CppUnitMini::ThreadPool pool( *this ); - pool.add( new insert_thread( pool, testSet ), c_nInsThreadCount ); - pool.add( new delete_thread( pool, testSet ), c_nDelThreadCount ? c_nDelThreadCount : cds::OS::topology::processor_count()); - pool.run(); - CPPUNIT_MSG( " Duration=" << pool.avgDuration() ); - - size_t nInsertSuccess = 0; - size_t nInsertFailed = 0; - size_t nDeleteSuccess = 0; - size_t nDeleteFailed = 0; - for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) { - insert_thread * pThread = dynamic_cast( *it ); - if ( pThread ) { - nInsertSuccess += pThread->m_nInsertSuccess; - nInsertFailed += pThread->m_nInsertFailed; - } - else { - delete_thread * p = static_cast( *it ); - nDeleteSuccess += p->m_nDeleteSuccess; - nDeleteFailed += p->m_nDeleteFailed; - } - } - - CPPUNIT_CHECK( nInsertSuccess == c_nSetSize * c_nInsThreadCount ); - CPPUNIT_CHECK( nInsertFailed == 0 ); - - CPPUNIT_MSG( " Totals (success/failed): \n\t" - << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t" - << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t" - ); - } - - template - void do_test_extract_with( Set& testSet ) - { - typedef InsertThread insert_thread; - typedef DeleteThread delete_thread; - typedef ExtractThread< typename Set::gc, Set > extract_thread; - - m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release ); - - CppUnitMini::ThreadPool pool( *this ); - pool.add( new insert_thread( pool, testSet ), c_nInsThreadCount ); - if ( c_nDelThreadCount ) - pool.add( new delete_thread( pool, testSet ), c_nDelThreadCount ); - if ( c_nExtractThreadCount ) - pool.add( new extract_thread( pool, testSet ), c_nExtractThreadCount ); - pool.run(); - CPPUNIT_MSG( " Duration=" << pool.avgDuration() ); - - size_t nInsertSuccess = 0; - size_t nInsertFailed = 0; - size_t nDeleteSuccess = 0; - size_t nDeleteFailed = 0; - size_t nExtractSuccess = 0; - size_t nExtractFailed = 0; - for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) { - insert_thread * pThread = dynamic_cast( *it ); - if ( pThread ) { - nInsertSuccess += pThread->m_nInsertSuccess; - nInsertFailed += pThread->m_nInsertFailed; - } - else { - delete_thread * p = dynamic_cast( *it ); - if ( p ) { - nDeleteSuccess += p->m_nDeleteSuccess; - nDeleteFailed += p->m_nDeleteFailed; - } - else { - extract_thread * pExt = dynamic_cast( *it ); - assert( pExt ); - nExtractSuccess += pExt->m_nExtractSuccess; - nExtractFailed += pExt->m_nExtractFailed; - } - } - } - - CPPUNIT_CHECK( nInsertSuccess == c_nSetSize * c_nInsThreadCount ); - CPPUNIT_CHECK( nInsertFailed == 0 ); - - CPPUNIT_MSG( " Totals (success/failed): \n\t" - << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t" - << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t" - << " Extract=" << nExtractSuccess << '/' << nExtractFailed << "\n\t" - ); - } - - template - void analyze( Set& testSet ) - { - // All even keys must be in the set - { - CPPUNIT_MSG( " Check even keys..." ); - size_t nErrorCount = 0; - for ( size_t n = 0; n < c_nSetSize; n +=2 ) { - for ( size_t i = 0; i < c_nInsThreadCount; ++i ) { - if ( !testSet.find( key_type(n, i) ) ) { - if ( ++nErrorCount < 10 ) { - CPPUNIT_MSG( "key " << n << "-" << i << " is not found!"); - } - } - } - } - CPPUNIT_CHECK_EX( nErrorCount == 0, "Totals: " << nErrorCount << " keys is not found"); - } - - check_before_clear( testSet ); - - CPPUNIT_MSG( " Clear map (single-threaded)..." ); - cds::OS::Timer timer; - testSet.clear(); - CPPUNIT_MSG( " Duration=" << timer.duration() ); - CPPUNIT_CHECK_EX( testSet.empty(), ((long long) testSet.size()) ); - - additional_check( testSet ); - print_stat( testSet ); - additional_cleanup( testSet ); - } - - template - void test() - { - CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount - << " delete thread count=" << c_nDelThreadCount - << " set size=" << c_nSetSize - ); - - for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) { - CPPUNIT_MSG( "Load factor=" << nLoadFactor ); - do_test( nLoadFactor ); - if ( c_bPrintGCState ) - print_gc_state(); - } - } - - template - void test_extract() - { - CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount - << " delete thread count=" << c_nDelThreadCount - << " extract thread count=" << c_nExtractThreadCount - << " set size=" << c_nSetSize - ); - - for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) { - CPPUNIT_MSG( "Load factor=" << nLoadFactor ); - do_test_extract( nLoadFactor ); - if ( c_bPrintGCState ) - print_gc_state(); - } - } - - template - void test_nolf() - { - CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount - << " delete thread count=" << c_nDelThreadCount - << " set size=" << c_nSetSize - ); - - { - Set s; - do_test_with( s ); - analyze( s ); - } - - if ( c_bPrintGCState ) - print_gc_state(); - } - - template - void test_nolf_extract() - { - CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount - << " delete thread count=" << c_nDelThreadCount - << " extract thread count=" << c_nExtractThreadCount - << " set size=" << c_nSetSize - ); - - { - Set s; - do_test_extract_with( s ); - analyze( s ); - } - - if ( c_bPrintGCState ) - print_gc_state(); - } - - void setUpParams( const CppUnitMini::TestCfg& cfg ) { - c_nSetSize = cfg.getULong("MapSize", static_cast(c_nSetSize) ); - c_nInsThreadCount = cfg.getULong("InsThreadCount", static_cast(c_nInsThreadCount) ); - c_nDelThreadCount = cfg.getULong("DelThreadCount", static_cast(c_nDelThreadCount) ); - c_nExtractThreadCount = cfg.getULong("ExtractThreadCount", static_cast(c_nExtractThreadCount) ); - c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", static_cast(c_nMaxLoadFactor) ); - c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true ); - - if ( c_nInsThreadCount == 0 ) - c_nInsThreadCount = cds::OS::topology::processor_count(); - if ( c_nDelThreadCount == 0 && c_nExtractThreadCount == 0 ) { - c_nExtractThreadCount = cds::OS::topology::processor_count() / 2; - c_nDelThreadCount = cds::OS::topology::processor_count() - c_nExtractThreadCount; - } - - m_arrData.resize( c_nSetSize ); - for ( size_t i = 0; i < c_nSetSize; ++i ) - m_arrData[i] = i; - std::random_shuffle( m_arrData.begin(), m_arrData.end() ); - } - -# include "set2/set_defs.h" - CDSUNIT_DECLARE_MichaelSet - CDSUNIT_DECLARE_SplitList - //CDSUNIT_DECLARE_StripedSet - //CDSUNIT_DECLARE_RefinableSet - CDSUNIT_DECLARE_CuckooSet - CDSUNIT_DECLARE_SkipListSet - CDSUNIT_DECLARE_EllenBinTreeSet - //CDSUNIT_DECLARE_StdSet - - CPPUNIT_TEST_SUITE_( Set_DelOdd, "Map_DelOdd" ) - CDSUNIT_TEST_MichaelSet - CDSUNIT_TEST_SplitList - CDSUNIT_TEST_SkipListSet - CDSUNIT_TEST_EllenBinTreeSet - //CDSUNIT_TEST_StripedSet - //CDSUNIT_TEST_RefinableSet - CDSUNIT_TEST_CuckooSet - //CDSUNIT_TEST_StdSet - CPPUNIT_TEST_SUITE_END() - }; - - CPPUNIT_TEST_SUITE_REGISTRATION( Set_DelOdd ); } // namespace set2 diff --git a/tests/unit/set2/set_delodd.h b/tests/unit/set2/set_delodd.h new file mode 100644 index 00000000..f06102c9 --- /dev/null +++ b/tests/unit/set2/set_delodd.h @@ -0,0 +1,752 @@ +//$$CDS-header$$ + +#include "cppunit/thread.h" +#include "set2/set_types.h" +#include // random_shuffle + +namespace set2 { + +# define TEST_SET(X) void X() { test::X >() ; } +# define TEST_SET_EXTRACT(X) void X() { test_extract::X >() ; } +# define TEST_SET_NOLF(X) void X() { test_nolf::X >() ; } +# define TEST_SET_NOLF_EXTRACT(X) void X() { test_nolf_extract::X >() ; } + + namespace { + struct key_thread + { + size_t nKey; + size_t nThread; + + key_thread( size_t key, size_t threadNo ) + : nKey( key ) + , nThread( threadNo ) + {} + + key_thread() + {} + }; + + typedef SetTypes::key_val key_value_pair; + } + + template <> + struct cmp { + int operator ()(key_thread const& k1, key_thread const& k2) const + { + if ( k1.nKey < k2.nKey ) + return -1; + if ( k1.nKey > k2.nKey ) + return 1; + if ( k1.nThread < k2.nThread ) + return -1; + if ( k1.nThread > k2.nThread ) + return 1; + return 0; + } + int operator ()(key_thread const& k1, size_t k2) const + { + if ( k1.nKey < k2 ) + return -1; + if ( k1.nKey > k2 ) + return 1; + return 0; + } + int operator ()(size_t k1, key_thread const& k2) const + { + if ( k1 < k2.nKey ) + return -1; + if ( k1 > k2.nKey ) + return 1; + return 0; + } + }; + +} // namespace set2 + +namespace std { + template <> + struct less + { + bool operator()(set2::key_thread const& k1, set2::key_thread const& k2) const + { + if ( k1.nKey <= k2.nKey ) + return k1.nKey < k2.nKey || k1.nThread < k2.nThread; + return false; + } + }; + + template <> + struct hash + { + typedef size_t result_type; + typedef set2::key_thread argument_type; + + size_t operator()( set2::key_thread const& k ) const + { + return std::hash()(k.nKey); + } + size_t operator()( size_t k ) const + { + return std::hash()(k); + } + }; + +} // namespace std + +namespace boost { + inline size_t hash_value( set2::key_thread const& k ) + { + return std::hash()( k.nKey ); + } + + template <> + struct hash + { + typedef size_t result_type; + typedef set2::key_thread argument_type; + + size_t operator()(set2::key_thread const& k) const + { + return boost::hash()( k.nKey ); + } + size_t operator()(size_t k) const + { + return boost::hash()( k ); + } + }; +} // namespace boost + +namespace set2 { + + class Set_DelOdd: public CppUnitMini::TestCase + { + static size_t c_nSetSize; // max set size + static size_t c_nInsThreadCount; // insert thread count + static size_t c_nDelThreadCount; // delete thread count + static size_t c_nExtractThreadCount; // extract thread count + static size_t c_nMaxLoadFactor; // maximum load factor + static bool c_bPrintGCState; + + std::vector m_arrData; + + protected: + typedef CppUnitMini::TestCase Base; + typedef key_thread key_type; + typedef size_t value_type; + + atomics::atomic m_nInsThreadCount; + + // Inserts keys from [0..N) + template + class InsertThread: public CppUnitMini::TestThread + { + Set& m_Set; + + virtual InsertThread * clone() + { + return new InsertThread( *this ); + } + + struct ensure_func + { + template + void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) + {} + }; + public: + size_t m_nInsertSuccess; + size_t m_nInsertFailed; + + public: + InsertThread( CppUnitMini::ThreadPool& pool, Set& rMap ) + : CppUnitMini::TestThread( pool ) + , m_Set( rMap ) + {} + InsertThread( InsertThread& src ) + : CppUnitMini::TestThread( src ) + , m_Set( src.m_Set ) + {} + + Set_DelOdd& getTest() + { + return reinterpret_cast( m_Pool.m_Test ); + } + + virtual void init() { cds::threading::Manager::attachThread() ; } + virtual void fini() { cds::threading::Manager::detachThread() ; } + + virtual void test() + { + Set& rSet = m_Set; + + m_nInsertSuccess = + m_nInsertFailed = 0; + + std::vector& arrData = getTest().m_arrData; + for ( size_t i = 0; i < arrData.size(); ++i ) { + if ( rSet.insert( key_type( arrData[i], m_nThreadNo ))) + ++m_nInsertSuccess; + else + ++m_nInsertFailed; + } + + ensure_func f; + for ( size_t i = arrData.size() - 1; i > 0; --i ) { + if ( arrData[i] & 1 ) { + rSet.ensure( key_type( arrData[i], m_nThreadNo ), f ); + } + } + + getTest().m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release ); + } + }; + + struct key_equal { + bool operator()( key_type const& k1, key_type const& k2 ) const + { + return k1.nKey == k2.nKey; + } + bool operator()( size_t k1, key_type const& k2 ) const + { + return k1 == k2.nKey; + } + bool operator()( key_type const& k1, size_t k2 ) const + { + return k1.nKey == k2; + } + bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const + { + return operator()( k1.key, k2.key ); + } + bool operator ()( key_value_pair const& k1, key_type const& k2 ) const + { + return operator()( k1.key, k2 ); + } + bool operator ()( key_type const& k1, key_value_pair const& k2 ) const + { + return operator()( k1, k2.key ); + } + bool operator ()( key_value_pair const& k1, size_t k2 ) const + { + return operator()( k1.key, k2 ); + } + bool operator ()( size_t k1, key_value_pair const& k2 ) const + { + return operator()( k1, k2.key ); + } + }; + + struct key_less { + bool operator()( key_type const& k1, key_type const& k2 ) const + { + return k1.nKey < k2.nKey; + } + bool operator()( size_t k1, key_type const& k2 ) const + { + return k1 < k2.nKey; + } + bool operator()( key_type const& k1, size_t k2 ) const + { + return k1.nKey < k2; + } + bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const + { + return operator()( k1.key, k2.key ); + } + bool operator ()( key_value_pair const& k1, key_type const& k2 ) const + { + return operator()( k1.key, k2 ); + } + bool operator ()( key_type const& k1, key_value_pair const& k2 ) const + { + return operator()( k1, k2.key ); + } + bool operator ()( key_value_pair const& k1, size_t k2 ) const + { + return operator()( k1.key, k2 ); + } + bool operator ()( size_t k1, key_value_pair const& k2 ) const + { + return operator()( k1, k2.key ); + } + + typedef key_equal equal_to; + }; + + // Deletes odd keys from [0..N) + template + class DeleteThread: public CppUnitMini::TestThread + { + Set& m_Set; + + virtual DeleteThread * clone() + { + return new DeleteThread( *this ); + } + public: + size_t m_nDeleteSuccess; + size_t m_nDeleteFailed; + + public: + DeleteThread( CppUnitMini::ThreadPool& pool, Set& rMap ) + : CppUnitMini::TestThread( pool ) + , m_Set( rMap ) + {} + DeleteThread( DeleteThread& src ) + : CppUnitMini::TestThread( src ) + , m_Set( src.m_Set ) + {} + + Set_DelOdd& getTest() + { + return reinterpret_cast( m_Pool.m_Test ); + } + + virtual void init() { cds::threading::Manager::attachThread() ; } + virtual void fini() { cds::threading::Manager::detachThread() ; } + + virtual void test() + { + Set& rSet = m_Set; + + m_nDeleteSuccess = + m_nDeleteFailed = 0; + + std::vector& arrData = getTest().m_arrData; + if ( m_nThreadNo & 1 ) { + for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { + for ( size_t i = 0; i < arrData.size(); ++i ) { + if ( arrData[i] & 1 ) { + if ( rSet.erase_with( arrData[i], key_less() )) + ++m_nDeleteSuccess; + else + ++m_nDeleteFailed; + } + } + if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) + break; + } + } + else { + for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { + for ( size_t i = arrData.size() - 1; i > 0; --i ) { + if ( arrData[i] & 1 ) { + if ( rSet.erase_with( arrData[i], key_less() )) + ++m_nDeleteSuccess; + else + ++m_nDeleteFailed; + } + } + if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) + break; + } + } + } + }; + + // Extracts odd keys from [0..N) + template + class ExtractThread: public CppUnitMini::TestThread + { + Set& m_Set; + + virtual ExtractThread * clone() + { + return new ExtractThread( *this ); + } + public: + size_t m_nExtractSuccess; + size_t m_nExtractFailed; + + public: + ExtractThread( CppUnitMini::ThreadPool& pool, Set& rMap ) + : CppUnitMini::TestThread( pool ) + , m_Set( rMap ) + {} + ExtractThread( ExtractThread& src ) + : CppUnitMini::TestThread( src ) + , m_Set( src.m_Set ) + {} + + Set_DelOdd& getTest() + { + return reinterpret_cast( m_Pool.m_Test ); + } + + virtual void init() { cds::threading::Manager::attachThread() ; } + virtual void fini() { cds::threading::Manager::detachThread() ; } + + virtual void test() + { + Set& rSet = m_Set; + + m_nExtractSuccess = + m_nExtractFailed = 0; + + typename Set::guarded_ptr gp; + + std::vector& arrData = getTest().m_arrData; + if ( m_nThreadNo & 1 ) { + for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { + for ( size_t i = 0; i < arrData.size(); ++i ) { + if ( arrData[i] & 1 ) { + gp = rSet.extract_with( arrData[i], key_less()); + if ( gp ) + ++m_nExtractSuccess; + else + ++m_nExtractFailed; + gp.release(); + } + } + if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) + break; + } + } + else { + for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { + for ( size_t i = arrData.size() - 1; i > 0; --i ) { + if ( arrData[i] & 1 ) { + gp = rSet.extract_with( arrData[i], key_less()); + if ( gp ) + ++m_nExtractSuccess; + else + ++m_nExtractFailed; + gp.release(); + } + } + if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) + break; + } + } + } + }; + + template + class ExtractThread< cds::urcu::gc, Set >: public CppUnitMini::TestThread + { + Set& m_Set; + + virtual ExtractThread * clone() + { + return new ExtractThread( *this ); + } + public: + size_t m_nExtractSuccess; + size_t m_nExtractFailed; + + public: + ExtractThread( CppUnitMini::ThreadPool& pool, Set& rMap ) + : CppUnitMini::TestThread( pool ) + , m_Set( rMap ) + {} + ExtractThread( ExtractThread& src ) + : CppUnitMini::TestThread( src ) + , m_Set( src.m_Set ) + {} + + Set_DelOdd& getTest() + { + return reinterpret_cast( m_Pool.m_Test ); + } + + virtual void init() { cds::threading::Manager::attachThread() ; } + virtual void fini() { cds::threading::Manager::detachThread() ; } + + virtual void test() + { + Set& rSet = m_Set; + + m_nExtractSuccess = + m_nExtractFailed = 0; + + typename Set::exempt_ptr xp; + + std::vector& arrData = getTest().m_arrData; + if ( m_nThreadNo & 1 ) { + for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { + for ( size_t i = 0; i < arrData.size(); ++i ) { + if ( arrData[i] & 1 ) { + if ( Set::c_bExtractLockExternal ) { + typename Set::rcu_lock l; + xp = rSet.extract_with( arrData[i], key_less() ); + if ( xp ) + ++m_nExtractSuccess; + else + ++m_nExtractFailed; + } + else { + xp = rSet.extract_with( arrData[i], key_less() ); + if ( xp ) + ++m_nExtractSuccess; + else + ++m_nExtractFailed; + } + xp.release(); + } + } + if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) + break; + } + } + else { + for ( size_t k = 0; k < c_nInsThreadCount; ++k ) { + for ( size_t i = arrData.size() - 1; i > 0; --i ) { + if ( arrData[i] & 1 ) { + if ( Set::c_bExtractLockExternal ) { + typename Set::rcu_lock l; + xp = rSet.extract_with( arrData[i], key_less() ); + if ( xp ) + ++m_nExtractSuccess; + else + ++m_nExtractFailed; + } + else { + xp = rSet.extract_with( arrData[i], key_less() ); + if ( xp ) + ++m_nExtractSuccess; + else + ++m_nExtractFailed; + } + xp.release(); + } + } + if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) + break; + } + } + } + }; + + protected: + template + void do_test( size_t nLoadFactor ) + { + Set testSet( c_nSetSize, nLoadFactor ); + do_test_with( testSet ); + analyze( testSet ); + } + + template + void do_test_extract( size_t nLoadFactor ) + { + Set testSet( c_nSetSize, nLoadFactor ); + do_test_extract_with( testSet ); + analyze( testSet ); + } + + template + void do_test_with( Set& testSet ) + { + typedef InsertThread insert_thread; + typedef DeleteThread delete_thread; + + m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release ); + + CppUnitMini::ThreadPool pool( *this ); + pool.add( new insert_thread( pool, testSet ), c_nInsThreadCount ); + pool.add( new delete_thread( pool, testSet ), c_nDelThreadCount ? c_nDelThreadCount : cds::OS::topology::processor_count()); + pool.run(); + CPPUNIT_MSG( " Duration=" << pool.avgDuration() ); + + size_t nInsertSuccess = 0; + size_t nInsertFailed = 0; + size_t nDeleteSuccess = 0; + size_t nDeleteFailed = 0; + for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) { + insert_thread * pThread = dynamic_cast( *it ); + if ( pThread ) { + nInsertSuccess += pThread->m_nInsertSuccess; + nInsertFailed += pThread->m_nInsertFailed; + } + else { + delete_thread * p = static_cast( *it ); + nDeleteSuccess += p->m_nDeleteSuccess; + nDeleteFailed += p->m_nDeleteFailed; + } + } + + CPPUNIT_CHECK( nInsertSuccess == c_nSetSize * c_nInsThreadCount ); + CPPUNIT_CHECK( nInsertFailed == 0 ); + + CPPUNIT_MSG( " Totals (success/failed): \n\t" + << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t" + << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t" + ); + } + + template + void do_test_extract_with( Set& testSet ) + { + typedef InsertThread insert_thread; + typedef DeleteThread delete_thread; + typedef ExtractThread< typename Set::gc, Set > extract_thread; + + m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release ); + + CppUnitMini::ThreadPool pool( *this ); + pool.add( new insert_thread( pool, testSet ), c_nInsThreadCount ); + if ( c_nDelThreadCount ) + pool.add( new delete_thread( pool, testSet ), c_nDelThreadCount ); + if ( c_nExtractThreadCount ) + pool.add( new extract_thread( pool, testSet ), c_nExtractThreadCount ); + pool.run(); + CPPUNIT_MSG( " Duration=" << pool.avgDuration() ); + + size_t nInsertSuccess = 0; + size_t nInsertFailed = 0; + size_t nDeleteSuccess = 0; + size_t nDeleteFailed = 0; + size_t nExtractSuccess = 0; + size_t nExtractFailed = 0; + for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) { + insert_thread * pThread = dynamic_cast( *it ); + if ( pThread ) { + nInsertSuccess += pThread->m_nInsertSuccess; + nInsertFailed += pThread->m_nInsertFailed; + } + else { + delete_thread * p = dynamic_cast( *it ); + if ( p ) { + nDeleteSuccess += p->m_nDeleteSuccess; + nDeleteFailed += p->m_nDeleteFailed; + } + else { + extract_thread * pExt = dynamic_cast( *it ); + assert( pExt ); + nExtractSuccess += pExt->m_nExtractSuccess; + nExtractFailed += pExt->m_nExtractFailed; + } + } + } + + CPPUNIT_CHECK( nInsertSuccess == c_nSetSize * c_nInsThreadCount ); + CPPUNIT_CHECK( nInsertFailed == 0 ); + + CPPUNIT_MSG( " Totals (success/failed): \n\t" + << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t" + << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t" + << " Extract=" << nExtractSuccess << '/' << nExtractFailed << "\n\t" + ); + } + + template + void analyze( Set& testSet ) + { + // All even keys must be in the set + { + CPPUNIT_MSG( " Check even keys..." ); + size_t nErrorCount = 0; + for ( size_t n = 0; n < c_nSetSize; n +=2 ) { + for ( size_t i = 0; i < c_nInsThreadCount; ++i ) { + if ( !testSet.find( key_type(n, i) ) ) { + if ( ++nErrorCount < 10 ) { + CPPUNIT_MSG( "key " << n << "-" << i << " is not found!"); + } + } + } + } + CPPUNIT_CHECK_EX( nErrorCount == 0, "Totals: " << nErrorCount << " keys is not found"); + } + + check_before_clear( testSet ); + + CPPUNIT_MSG( " Clear map (single-threaded)..." ); + cds::OS::Timer timer; + testSet.clear(); + CPPUNIT_MSG( " Duration=" << timer.duration() ); + CPPUNIT_CHECK_EX( testSet.empty(), ((long long) testSet.size()) ); + + additional_check( testSet ); + print_stat( testSet ); + additional_cleanup( testSet ); + } + + template + void test() + { + CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount + << " delete thread count=" << c_nDelThreadCount + << " set size=" << c_nSetSize + ); + + for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) { + CPPUNIT_MSG( "Load factor=" << nLoadFactor ); + do_test( nLoadFactor ); + if ( c_bPrintGCState ) + print_gc_state(); + } + } + + template + void test_extract() + { + CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount + << " delete thread count=" << c_nDelThreadCount + << " extract thread count=" << c_nExtractThreadCount + << " set size=" << c_nSetSize + ); + + for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) { + CPPUNIT_MSG( "Load factor=" << nLoadFactor ); + do_test_extract( nLoadFactor ); + if ( c_bPrintGCState ) + print_gc_state(); + } + } + + template + void test_nolf() + { + CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount + << " delete thread count=" << c_nDelThreadCount + << " set size=" << c_nSetSize + ); + + { + Set s; + do_test_with( s ); + analyze( s ); + } + + if ( c_bPrintGCState ) + print_gc_state(); + } + + template + void test_nolf_extract() + { + CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount + << " delete thread count=" << c_nDelThreadCount + << " extract thread count=" << c_nExtractThreadCount + << " set size=" << c_nSetSize + ); + + { + Set s; + do_test_extract_with( s ); + analyze( s ); + } + + if ( c_bPrintGCState ) + print_gc_state(); + } + + void setUpParams( const CppUnitMini::TestCfg& cfg ); + + void run_MichaelSet(const char *in_name, bool invert = false); + void run_SplitList(const char *in_name, bool invert = false); + void run_CuckooSet(const char *in_name, bool invert = false); + void run_SkipListSet(const char *in_name, bool invert = false); + void run_EllenBinTreeSet(const char *in_name, bool invert = false); + + virtual void myRun(const char *in_name, bool invert = false); + + +# include "set2/set_defs.h" + CDSUNIT_DECLARE_MichaelSet + CDSUNIT_DECLARE_SplitList + CDSUNIT_DECLARE_CuckooSet + CDSUNIT_DECLARE_SkipListSet + CDSUNIT_DECLARE_EllenBinTreeSet + }; +} // namespace set2 diff --git a/tests/unit/set2/set_delodd_cuckoo.cpp b/tests/unit/set2/set_delodd_cuckoo.cpp new file mode 100644 index 00000000..80ca8d5c --- /dev/null +++ b/tests/unit/set2/set_delodd_cuckoo.cpp @@ -0,0 +1,10 @@ +//$$CDS-header$$ + +#include "set2/set_delodd.h" + +namespace set2 { + CPPUNIT_TEST_SUITE_PART( Set_DelOdd, run_CuckooSet ) + CDSUNIT_TEST_CuckooSet + CPPUNIT_TEST_SUITE_END_PART() + +} // namespace set2 diff --git a/tests/unit/set2/set_delodd_ellentree.cpp b/tests/unit/set2/set_delodd_ellentree.cpp new file mode 100644 index 00000000..6bd29b49 --- /dev/null +++ b/tests/unit/set2/set_delodd_ellentree.cpp @@ -0,0 +1,10 @@ +//$$CDS-header$$ + +#include "set2/set_delodd.h" + +namespace set2 { + CPPUNIT_TEST_SUITE_PART( Set_DelOdd, run_EllenBinTreeSet ) + CDSUNIT_TEST_EllenBinTreeSet + CPPUNIT_TEST_SUITE_END_PART() + +} // namespace set2 diff --git a/tests/unit/set2/set_delodd_michael.cpp b/tests/unit/set2/set_delodd_michael.cpp new file mode 100644 index 00000000..a9884721 --- /dev/null +++ b/tests/unit/set2/set_delodd_michael.cpp @@ -0,0 +1,10 @@ +//$$CDS-header$$ + +#include "set2/set_delodd.h" + +namespace set2 { + CPPUNIT_TEST_SUITE_PART( Set_DelOdd, run_MichaelSet ) + CDSUNIT_TEST_MichaelSet + CPPUNIT_TEST_SUITE_END_PART() + +} // namespace set2 diff --git a/tests/unit/set2/set_delodd_skip.cpp b/tests/unit/set2/set_delodd_skip.cpp new file mode 100644 index 00000000..2a072999 --- /dev/null +++ b/tests/unit/set2/set_delodd_skip.cpp @@ -0,0 +1,10 @@ +//$$CDS-header$$ + +#include "set2/set_delodd.h" + +namespace set2 { + CPPUNIT_TEST_SUITE_PART( Set_DelOdd, run_SkipListSet ) + CDSUNIT_TEST_SkipListSet + CPPUNIT_TEST_SUITE_END_PART() + +} // namespace set2 diff --git a/tests/unit/set2/set_delodd_split.cpp b/tests/unit/set2/set_delodd_split.cpp new file mode 100644 index 00000000..85e8ba08 --- /dev/null +++ b/tests/unit/set2/set_delodd_split.cpp @@ -0,0 +1,10 @@ +//$$CDS-header$$ + +#include "set2/set_delodd.h" + +namespace set2 { + CPPUNIT_TEST_SUITE_PART( Set_DelOdd, run_SplitList ) + CDSUNIT_TEST_SplitList + CPPUNIT_TEST_SUITE_END_PART() + +} // namespace set2 diff --git a/tests/unit/set2/set_insdel_func6.cpp b/tests/unit/set2/set_insdel_func_cuckoo.cpp similarity index 100% rename from tests/unit/set2/set_insdel_func6.cpp rename to tests/unit/set2/set_insdel_func_cuckoo.cpp diff --git a/tests/unit/set2/set_insdel_func7.cpp b/tests/unit/set2/set_insdel_func_ellentree.cpp similarity index 100% rename from tests/unit/set2/set_insdel_func7.cpp rename to tests/unit/set2/set_insdel_func_ellentree.cpp diff --git a/tests/unit/set2/set_insdel_func5.cpp b/tests/unit/set2/set_insdel_func_refinable.cpp similarity index 100% rename from tests/unit/set2/set_insdel_func5.cpp rename to tests/unit/set2/set_insdel_func_refinable.cpp diff --git a/tests/unit/set2/set_insdel_func3.cpp b/tests/unit/set2/set_insdel_func_skip.cpp similarity index 100% rename from tests/unit/set2/set_insdel_func3.cpp rename to tests/unit/set2/set_insdel_func_skip.cpp diff --git a/tests/unit/set2/set_insdel_func2.cpp b/tests/unit/set2/set_insdel_func_split.cpp similarity index 100% rename from tests/unit/set2/set_insdel_func2.cpp rename to tests/unit/set2/set_insdel_func_split.cpp diff --git a/tests/unit/set2/set_insdel_func4.cpp b/tests/unit/set2/set_insdel_func_striped.cpp similarity index 100% rename from tests/unit/set2/set_insdel_func4.cpp rename to tests/unit/set2/set_insdel_func_striped.cpp diff --git a/tests/unit/set2/set_types.h b/tests/unit/set2/set_types.h index a048eb37..1e163239 100644 --- a/tests/unit/set2/set_types.h +++ b/tests/unit/set2/set_types.h @@ -1806,6 +1806,20 @@ namespace set2 { ellen_bintree_pool::internal_node_counter::reset(); } + //******************************************************* + // check_before_clear + //******************************************************* + + template + static inline void check_before_clear( Set& /*s*/ ) + {} + + template + static inline void check_before_clear( cds::container::EllenBinTreeSet& s ) + { + CPPUNIT_CHECK_CURRENT( s.check_consistency() ); + } + } // namespace set2 #endif // ifndef CDSUNIT_SET_TYPES_H -- 2.34.1