From a01d829dfe98ba09786c202eda2c78fc0491f5ea Mon Sep 17 00:00:00 2001 From: khizmax Date: Sat, 5 Sep 2015 18:21:04 +0300 Subject: [PATCH] StripedMap: replace ensure() with update(), find(key) with contains(key) Refactored Map_InsDel_func MT-test --- cds/container/striped_map.h | 70 +++--- cds/container/striped_map/boost_list.h | 5 +- cds/container/striped_map/boost_slist.h | 5 +- cds/container/striped_map/std_hash_map.h | 17 +- cds/container/striped_map/std_list.h | 5 +- cds/container/striped_map/std_map.h | 17 +- cds/container/striped_set/adapter.h | 25 +- projects/Win/vc12/unit-map-insdel.vcxproj | 2 +- .../Win/vc12/unit-map-insdel.vcxproj.filters | 6 +- projects/source.unit.map.mk | 10 +- tests/data/test-debug.conf | 11 +- tests/data/test-express.conf | 11 +- tests/data/test.conf | 10 +- tests/unit/map2/CMakeLists.txt | 10 +- tests/unit/map2/map_insdel_func.cpp | 45 +--- tests/unit/map2/map_insdel_func.h | 218 ++++++++++-------- .../map2/map_insdel_func_bronsonavltree.cpp | 10 +- tests/unit/map2/map_insdel_func_cuckoo.cpp | 10 +- tests/unit/map2/map_insdel_func_ellentree.cpp | 11 +- tests/unit/map2/map_insdel_func_michael.cpp | 10 +- .../map_insdel_func_multilevelhashmap.cpp | 12 + tests/unit/map2/map_insdel_func_refinable.cpp | 12 - tests/unit/map2/map_insdel_func_skip.cpp | 11 +- tests/unit/map2/map_insdel_func_split.cpp | 11 +- tests/unit/map2/map_insdel_func_striped.cpp | 11 +- 25 files changed, 315 insertions(+), 250 deletions(-) create mode 100644 tests/unit/map2/map_insdel_func_multilevelhashmap.cpp delete mode 100644 tests/unit/map2/map_insdel_func_refinable.cpp diff --git a/cds/container/striped_map.h b/cds/container/striped_map.h index a40e5d31..06739d92 100644 --- a/cds/container/striped_map.h +++ b/cds/container/striped_map.h @@ -636,37 +636,29 @@ template return bOk; } - /// Ensures that the \p key exists in the map + /// Updates the node /** The operation performs inserting or changing data with lock-free manner. - If the \p key not found in the map, then the new item created from \p key - is inserted into the map (note that in this case the \p key_type should be - constructible from type \p K). + If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with item found. - The functor \p Func may be a function with signature: - \code - void func( bool bNew, value_type& item ); - \endcode - or a functor: + + The functor signature is: \code struct my_functor { void operator()( bool bNew, value_type& item ); }; \endcode - with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - - \p item - item of the list - - The functor may change any fields of the \p item.second that is \p mapped_type. + - \p item - item of the map Returns std::pair where \p first is true if operation is successfull, \p second is true if new item has been added or \p false if the item with \p key - already is in the list. + already is in the map. */ template - std::pair ensure( K const& key, Func func ) + std::pair update( K const& key, Func func, bool bAllowInsert = true ) { std::pair result; bool bResize; @@ -676,7 +668,7 @@ template scoped_cell_lock sl( base_class::m_MutexPolicy, nHash ); pBucket = base_class::bucket( nHash ); - result = pBucket->ensure( key, func ); + result = pBucket->update( key, func, bAllowInsert ); bResize = result.first && result.second && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket ); } @@ -684,6 +676,13 @@ template base_class::resize(); return result; } + //@cond + template + CDS_DEPRECATED("ensure() is deprecated, use update() instead") + std::pair ensure( K const& key, Func func ) + { + return update( key, func, true ); + } /// Delete \p key from the map /** \anchor cds_nonintrusive_StripedMap_erase @@ -796,36 +795,51 @@ template [&f]( value_type& pair, K const& ) mutable { f(pair); } ); } - /// Find the key \p key - /** \anchor cds_nonintrusive_StripedMap_find_val - + /// Checks whether the map contains \p key + /** The function searches the item with key equal to \p key and returns \p true if it is found, and \p false otherwise. */ template + bool contains( K const& key ) + { + return base_class::contains( key ); + } + //@cond + template + CDS_DEPRECATED("use contains()") bool find( K const& key ) { - return base_class::find( key ); + return contains( key ); } + //@endcond - /// Find the key \p val using \p pred predicate + /// Checks whether the set contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_StripedMap_find_val "find(K const&)" - but \p pred is used for key comparing - \p Less has the interface like \p std::less. - \p pred must imply the same element order as the comparator used for building the set. + The function is similar to contains( key ) but \p pred is used for key comparing. + \p Less functor has the interface like \p std::less. + \p Less must imply the same element order as the comparator used for building the set. @note This function is enabled if the compiler supports C++11 default template arguments for function template and the underlying container - supports \p %find_with feature. + supports \p %contains() feature. */ template ::type > - bool find_with( K const& key, Less pred ) + bool contains( K const& key, Less pred ) { CDS_UNUSED( pred ); - return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >() ); + return base_class::contains( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >() ); + } + //@cond + template ::type > + CDS_DEPRECATED("use contains()") + bool find_with( K const& key, Less pred ) + { + return contains( key, pred ); } + //@endcond /// Clears the map void clear() diff --git a/cds/container/striped_map/boost_list.h b/cds/container/striped_map/boost_list.h index a82b0bfa..92526c2e 100644 --- a/cds/container/striped_map/boost_list.h +++ b/cds/container/striped_map/boost_list.h @@ -161,11 +161,14 @@ namespace cds { namespace intrusive { namespace striped_set { } template - std::pair ensure( const Q& key, Func func ) + std::pair update( const Q& key, Func func, bool bAllowInsert ) { iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() ); if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) { // insert new + if ( !bAllowInsert ) + return std::make_pair( false, false ); + value_type newItem( key, mapped_type() ); it = m_List.insert( it, newItem ); func( true, *it ); diff --git a/cds/container/striped_map/boost_slist.h b/cds/container/striped_map/boost_slist.h index 5c361665..4ff101ee 100644 --- a/cds/container/striped_map/boost_slist.h +++ b/cds/container/striped_map/boost_slist.h @@ -172,11 +172,14 @@ namespace cds { namespace intrusive { namespace striped_set { } template - std::pair ensure( const Q& key, Func func ) + std::pair update( const Q& key, Func func, bool bAllowInsert ) { std::pair< iterator, bool > pos = find_prev_item( key ); if ( !pos.second ) { // insert new + if ( !bAllowInsert ) + return std::make_pair( false, false ); + value_type newItem( key, mapped_type() ); pos.first = m_List.insert_after( pos.first, newItem ); func( true, *pos.first ); diff --git a/cds/container/striped_map/std_hash_map.h b/cds/container/striped_map/std_hash_map.h index 6904505d..4173fb89 100644 --- a/cds/container/striped_map/std_hash_map.h +++ b/cds/container/striped_map/std_hash_map.h @@ -118,11 +118,20 @@ namespace cds { namespace intrusive { namespace striped_set { } template - std::pair ensure( const Q& key, Func func ) + std::pair update( const Q& key, Func func, bool bAllowInsert ) { - std::pair res = m_Map.insert( value_type( key, mapped_type() ) ); - func( res.second, const_cast(*res.first)); - return std::make_pair( true, res.second ); + if ( bAllowInsert ) { + std::pair res = m_Map.insert( value_type( key, mapped_type() ) ); + func( res.second, const_cast(*res.first)); + return std::make_pair( true, res.second ); + } + else { + auto it = m_Map.find(key_type( key )); + if ( it == end() ) + return std::make_pair( false, false ); + func( false, *it ); + return std::make_pair( true, false ); + } } template diff --git a/cds/container/striped_map/std_list.h b/cds/container/striped_map/std_list.h index 4e7bdc18..f25b1826 100644 --- a/cds/container/striped_map/std_list.h +++ b/cds/container/striped_map/std_list.h @@ -180,11 +180,14 @@ namespace cds { namespace intrusive { namespace striped_set { } template - std::pair ensure( const Q& key, Func func ) + std::pair update( const Q& key, Func func, bool bAllowInsert ) { iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() ); if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) { // insert new + if ( !bAllowInsert ) + return std::make_pair( false, false ); + value_type newItem( key, mapped_type() ); it = m_List.insert( it, newItem ); func( true, *it ); diff --git a/cds/container/striped_map/std_map.h b/cds/container/striped_map/std_map.h index 62a0c72f..a2f2fcdf 100644 --- a/cds/container/striped_map/std_map.h +++ b/cds/container/striped_map/std_map.h @@ -118,11 +118,20 @@ namespace cds { namespace intrusive { namespace striped_set { } template - std::pair ensure( const Q& key, Func func ) + std::pair update( const Q& key, Func func, bool bAllowInsert ) { - std::pair res = m_Map.insert( value_type( key, mapped_type() )); - func( res.second, *res.first ); - return std::make_pair( true, res.second ); + if ( bAllowInsert ) { + std::pair res = m_Map.insert( value_type( key, mapped_type() )); + func( res.second, *res.first ); + return std::make_pair( true, res.second ); + } + else { + auto it = m_Map.find(key_type( key )); + if ( it == end() ) + return std::make_pair( false, false ); + func( false, *it ); + return std::make_pair( true, false ); + } } template diff --git a/cds/container/striped_set/adapter.h b/cds/container/striped_set/adapter.h index b6deb8cc..ef60abe4 100644 --- a/cds/container/striped_set/adapter.h +++ b/cds/container/striped_set/adapter.h @@ -73,12 +73,12 @@ namespace cds { namespace container { variadic template and move semantics
- Ensures that the \p item exists in the container - \code template std::pair ensure( const Q& val, Func func ) \endcode + Updates \p item + \code template std::pair update( const Q& val, Func func, bool bAllowInsert ) \endcode The operation performs inserting or changing data. If the \p val key not found in the container, then the new item created from \p val - is inserted. Otherwise, the functor \p func is called with the item found. + is inserted iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with the item found. The \p Func functor has interface: \code void func( bool bNew, value_type& item, const Q& val ); @@ -93,7 +93,7 @@ namespace cds { namespace container { where arguments are: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - container's item - - \p val - argument \p val passed into the \p ensure function + - \p val - argument \p val passed into the \p update() function The functor can change non-key fields of the \p item. @@ -429,11 +429,20 @@ namespace cds { namespace container { } template - std::pair ensure( const Q& val, Func func ) + std::pair update( const Q& key, Func func, bool bAllowInsert ) { - std::pair res = m_Map.insert( value_type( val, mapped_type() )); - func( res.second, *res.first ); - return std::make_pair( true, res.second ); + if ( bAllowInsert ) { + std::pair res = m_Map.insert( value_type( key, mapped_type() )); + func( res.second, *res.first ); + return std::make_pair( true, res.second ); + } + else { + auto it = m_Map.find(key_type( key )); + if ( it == end() ) + return std::make_pair( false, false ); + func( false, *it ); + return std::make_pair( true, false ); + } } template diff --git a/projects/Win/vc12/unit-map-insdel.vcxproj b/projects/Win/vc12/unit-map-insdel.vcxproj index 48ce135a..fd0ee80b 100644 --- a/projects/Win/vc12/unit-map-insdel.vcxproj +++ b/projects/Win/vc12/unit-map-insdel.vcxproj @@ -48,7 +48,7 @@ - + diff --git a/projects/Win/vc12/unit-map-insdel.vcxproj.filters b/projects/Win/vc12/unit-map-insdel.vcxproj.filters index f3be91cd..c22d583e 100644 --- a/projects/Win/vc12/unit-map-insdel.vcxproj.filters +++ b/projects/Win/vc12/unit-map-insdel.vcxproj.filters @@ -16,9 +16,6 @@ map_insdel_func - - map_insdel_func - map_insdel_func @@ -88,6 +85,9 @@ map_insdel_int + + map_insdel_func + diff --git a/projects/source.unit.map.mk b/projects/source.unit.map.mk index accb9347..2264a10a 100644 --- a/projects/source.unit.map.mk +++ b/projects/source.unit.map.mk @@ -31,14 +31,14 @@ CDSUNIT_MAP_SOURCES := \ tests/unit/map2/map_insfind_int_refinable.cpp \ tests/unit/map2/map_insfind_int_std.cpp \ tests/unit/map2/map_insdel_func.cpp \ + tests/unit/map2/map_insdel_func_bronsonavltree.cpp \ + tests/unit/map2/map_insdel_func_cuckoo.cpp \ + tests/unit/map2/map_insdel_func_ellentree.cpp \ tests/unit/map2/map_insdel_func_michael.cpp \ - tests/unit/map2/map_insdel_func_split.cpp \ + tests/unit/map2/map_insdel_func_multilevelhashmap.cpp \ tests/unit/map2/map_insdel_func_skip.cpp \ - tests/unit/map2/map_insdel_func_ellentree.cpp \ - tests/unit/map2/map_insdel_func_bronsonavltree.cpp \ + tests/unit/map2/map_insdel_func_split.cpp \ tests/unit/map2/map_insdel_func_striped.cpp \ - tests/unit/map2/map_insdel_func_refinable.cpp \ - tests/unit/map2/map_insdel_func_cuckoo.cpp \ tests/unit/map2/map_insdel_int.cpp \ tests/unit/map2/map_insdel_int_bronsonavltree.cpp \ tests/unit/map2/map_insdel_int_cuckoo.cpp \ diff --git a/tests/data/test-debug.conf b/tests/data/test-debug.conf index 88c2207d..304feb9d 100644 --- a/tests/data/test-debug.conf +++ b/tests/data/test-debug.conf @@ -147,15 +147,22 @@ CuckooProbesetThreshold=0 MultiLevelMapHeadBits=8 MultiLevelMapArrayBits=4 - [Map_InsDel_func] InsertThreadCount=4 DeleteThreadCount=4 -EnsureThreadCount=4 +UpdateThreadCount=4 ThreadPassCount=8 MapSize=5000 MaxLoadFactor=4 PrintGCStateFlag=1 +# *** Cuckoo map properties +CuckooInitialSize=256 +CuckooProbesetSize=8 +# 0 - use default +CuckooProbesetThreshold=0 +# *** MultiLevelHashMap properties +MultiLevelMapHeadBits=8 +MultiLevelMapArrayBits=4 [Map_InsDel_Item_int] ThreadCount=4 diff --git a/tests/data/test-express.conf b/tests/data/test-express.conf index a177efdc..929420ce 100644 --- a/tests/data/test-express.conf +++ b/tests/data/test-express.conf @@ -145,15 +145,22 @@ CuckooProbesetThreshold=0 MultiLevelMapHeadBits=8 MultiLevelMapArrayBits=4 - [Map_InsDel_func] InsertThreadCount=4 DeleteThreadCount=4 -EnsureThreadCount=4 +UpdateThreadCount=4 ThreadPassCount=4 MapSize=100000 MaxLoadFactor=4 PrintGCStateFlag=1 +# *** Cuckoo map properties +CuckooInitialSize=1024 +CuckooProbesetSize=16 +# 0 - use default +CuckooProbesetThreshold=0 +# *** MultiLevelHashMap properties +MultiLevelMapHeadBits=8 +MultiLevelMapArrayBits=4 [Map_InsDel_Item_int] ThreadCount=8 diff --git a/tests/data/test.conf b/tests/data/test.conf index 97eafc50..d5be15c3 100644 --- a/tests/data/test.conf +++ b/tests/data/test.conf @@ -143,11 +143,19 @@ MultiLevelMapArrayBits=4 [Map_InsDel_func] InsertThreadCount=4 DeleteThreadCount=4 -EnsureThreadCount=4 +UpdateThreadCount=4 ThreadPassCount=2 MapSize=1000000 MaxLoadFactor=4 PrintGCStateFlag=1 +# *** Cuckoo map properties +CuckooInitialSize=1024 +CuckooProbesetSize=16 +# 0 - use default +CuckooProbesetThreshold=0 +# *** MultiLevelHashMap properties +MultiLevelMapHeadBits=10 +MultiLevelMapArrayBits=4 [Map_InsDel_Item_int] ThreadCount=8 diff --git a/tests/unit/map2/CMakeLists.txt b/tests/unit/map2/CMakeLists.txt index fbcddeec..95fc4fb5 100644 --- a/tests/unit/map2/CMakeLists.txt +++ b/tests/unit/map2/CMakeLists.txt @@ -32,14 +32,14 @@ set(CDSUNIT_MAP_SOURCES map_insfind_int_refinable.cpp map_insfind_int_std.cpp map_insdel_func.cpp + map_insdel_func_bronsonavltree.cpp + map_insdel_func_cuckoo.cpp + map_insdel_func_ellentree.cpp map_insdel_func_michael.cpp - map_insdel_func_split.cpp + map_insdel_func_multilevelhashmap.cpp map_insdel_func_skip.cpp - map_insdel_func_ellentree.cpp - map_insdel_func_bronsonavltree.cpp + map_insdel_func_split.cpp map_insdel_func_striped.cpp - map_insdel_func_refinable.cpp - map_insdel_func_cuckoo.cpp map_insdel_int.cpp map_insdel_int_bronsonavltree.cpp map_insdel_int_cuckoo.cpp diff --git a/tests/unit/map2/map_insdel_func.cpp b/tests/unit/map2/map_insdel_func.cpp index 964b38e9..f96723e1 100644 --- a/tests/unit/map2/map_insdel_func.cpp +++ b/tests/unit/map2/map_insdel_func.cpp @@ -5,45 +5,22 @@ namespace map2 { CPPUNIT_TEST_SUITE_REGISTRATION( Map_InsDel_func ); - static const size_t def_nMapSize = 1000000; - static const size_t def_nInsertThreadCount = 4; - static const size_t def_nDeleteThreadCount = 4; - static const size_t def_nEnsureThreadCount = 4; - static const size_t def_nThreadPassCount = 4; - static const size_t def_nMaxLoadFactor = 8; - - size_t Map_InsDel_func::c_nMapSize = def_nMapSize ; // map size - size_t Map_InsDel_func::c_nInsertThreadCount = def_nInsertThreadCount; // count of insertion thread - size_t Map_InsDel_func::c_nDeleteThreadCount = def_nDeleteThreadCount; // count of deletion thread - size_t Map_InsDel_func::c_nEnsureThreadCount = def_nEnsureThreadCount; // count of ensure thread - size_t Map_InsDel_func::c_nThreadPassCount = def_nThreadPassCount; // pass count for each thread - size_t Map_InsDel_func::c_nMaxLoadFactor = def_nMaxLoadFactor; // maximum load factor - bool Map_InsDel_func::c_bPrintGCState = true; - void Map_InsDel_func::setUpParams( const CppUnitMini::TestCfg& cfg ) { - c_nInsertThreadCount = cfg.getULong("InsertThreadCount", def_nInsertThreadCount ); - c_nDeleteThreadCount = cfg.getULong("DeleteThreadCount", def_nDeleteThreadCount ); - c_nEnsureThreadCount = cfg.getULong("EnsureThreadCount", def_nEnsureThreadCount ); - c_nThreadPassCount = cfg.getULong("ThreadPassCount", def_nThreadPassCount ); - c_nMapSize = cfg.getULong("MapSize", def_nMapSize ); - c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", def_nMaxLoadFactor ); + c_nInsertThreadCount = cfg.getULong("InsertThreadCount", static_cast(c_nInsertThreadCount)); + c_nDeleteThreadCount = cfg.getULong("DeleteThreadCount", static_cast(c_nDeleteThreadCount)); + c_nUpdateThreadCount = cfg.getULong("UpdateThreadCount", static_cast(c_nUpdateThreadCount)); + c_nThreadPassCount = cfg.getULong("ThreadPassCount", static_cast(c_nThreadPassCount)); + c_nMapSize = cfg.getULong("MapSize", static_cast(c_nMapSize)); + c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", static_cast(c_nMaxLoadFactor)); c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true ); - } - void Map_InsDel_func::myRun(const char *in_name, bool invert /*= false*/) - { - setUpParams( m_Cfg.get( "Map_InsDel_func" )); + c_nCuckooInitialSize = cfg.getULong("CuckooInitialSize", static_cast(c_nCuckooInitialSize) ); + c_nCuckooProbesetSize = cfg.getULong("CuckooProbesetSize", static_cast(c_nCuckooProbesetSize) ); + c_nCuckooProbesetThreshold = cfg.getULong("CuckooProbesetThreshold", static_cast(c_nCuckooProbesetThreshold) ); - run_MichaelMap(in_name, invert); - run_SplitList(in_name, invert); - run_SkipListMap(in_name, invert); - run_EllenBinTreeMap(in_name, invert); - run_BronsonAVLTreeMap(in_name, invert); - run_StripedMap(in_name, invert); - run_RefinableMap(in_name, invert); - run_CuckooMap(in_name, invert); + c_nMultiLevelMap_HeadBits = cfg.getULong("MultiLevelMapHeadBits", static_cast(c_nMultiLevelMap_HeadBits) ); + c_nMultiLevelMap_ArrayBits = cfg.getULong("MultiLevelMapArrayBits", static_cast(c_nMultiLevelMap_ArrayBits) ); - endTestCase(); } } // namespace map2 diff --git a/tests/unit/map2/map_insdel_func.h b/tests/unit/map2/map_insdel_func.h index e4e075b4..9294fae6 100644 --- a/tests/unit/map2/map_insdel_func.h +++ b/tests/unit/map2/map_insdel_func.h @@ -10,26 +10,39 @@ namespace map2 { -# define TEST_MAP(IMPL, C, X) void C::X() { test::X >() ; } -# define TEST_MAP_EXTRACT(IMPL, C, X) TEST_MAP(IMPL, C, X) -# define TEST_MAP_NOLF(IMPL, C, X) void C::X() { test_nolf::X >() ; } -# define TEST_MAP_NOLF_EXTRACT(IMPL, C, X) TEST_MAP_NOLF(IMPL, C, X) +# define TEST_CASE(TAG, X) void X(); + +//# define TEST_MAP(IMPL, C, X) void C::X() { test::X >() ; } +//# define TEST_MAP_EXTRACT(IMPL, C, X) TEST_MAP(IMPL, C, X) +//# define TEST_MAP_NOLF(IMPL, C, X) void C::X() { test_nolf::X >() ; } +//# define TEST_MAP_NOLF_EXTRACT(IMPL, C, X) TEST_MAP_NOLF(IMPL, C, X) class Map_InsDel_func: public CppUnitMini::TestCase { - static size_t c_nMapSize; // map size - static size_t c_nInsertThreadCount; // count of insertion thread - static size_t c_nDeleteThreadCount; // count of deletion thread - static size_t c_nEnsureThreadCount; // count of ensure thread - static size_t c_nThreadPassCount; // pass count for each thread - static size_t c_nMaxLoadFactor; // maximum load factor - static bool c_bPrintGCState; + public: + size_t c_nMapSize = 1000000; // map size + size_t c_nInsertThreadCount = 4; // count of insertion thread + size_t c_nDeleteThreadCount = 4; // count of deletion thread + size_t c_nUpdateThreadCount = 4; // count of updating thread + size_t c_nThreadPassCount = 4; // pass count for each thread + size_t c_nMaxLoadFactor = 8; // maximum load factor + bool c_bPrintGCState = true; + + size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap + size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset) + size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default) + + size_t c_nMultiLevelMap_HeadBits = 10; + size_t c_nMultiLevelMap_ArrayBits = 4; + size_t c_nLoadFactor; // current load factor + + private: typedef size_t key_type; struct value_type { size_t nKey; size_t nData; - atomics::atomic nEnsureCall; + atomics::atomic nUpdateCall; atomics::atomic bInitialized; cds::OS::ThreadId threadId ; // insert thread id @@ -39,7 +52,7 @@ namespace map2 { value_type() : nKey(0) , nData(0) - , nEnsureCall(0) + , nUpdateCall(0) , bInitialized( false ) , threadId( cds::OS::get_current_thread_id() ) {} @@ -47,7 +60,7 @@ namespace map2 { value_type( value_type const& s ) : nKey(s.nKey) , nData(s.nData) - , nEnsureCall(s.nEnsureCall.load(atomics::memory_order_relaxed)) + , nUpdateCall(s.nUpdateCall.load(atomics::memory_order_relaxed)) , bInitialized( s.bInitialized.load(atomics::memory_order_relaxed) ) , threadId( cds::OS::get_current_thread_id() ) {} @@ -57,7 +70,7 @@ namespace map2 { { nKey = v.nKey; nData = v.nData; - nEnsureCall.store( v.nEnsureCall.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed ); + nUpdateCall.store( v.nUpdateCall.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed ); bInitialized.store(v.bInitialized.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed); return *this; @@ -138,9 +151,10 @@ namespace map2 { // func is passed by reference insert_functor func; key_array const& arr = getTest().m_arrValues; + size_t const nPassCount = getTest().c_nThreadPassCount; if ( m_nThreadNo & 1 ) { - for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { + for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) { for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) { if ( rMap.insert_with( *it, std::ref(func) ) ) ++m_nInsertSuccess; @@ -150,7 +164,7 @@ namespace map2 { } } else { - for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { + for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) { for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) { if ( rMap.insert_with( *it, std::ref(func) ) ) ++m_nInsertSuccess; @@ -165,20 +179,20 @@ namespace map2 { }; template - class Ensurer: public CppUnitMini::TestThread + class Updater: public CppUnitMini::TestThread { Map& m_Map; - virtual Ensurer * clone() + virtual Updater * clone() { - return new Ensurer( *this ); + return new Updater( *this ); } - struct ensure_functor { + struct update_functor { size_t nCreated; size_t nModified; - ensure_functor() + update_functor() : nCreated(0) , nModified(0) {} @@ -194,7 +208,7 @@ namespace map2 { v.bInitialized.store( true, atomics::memory_order_relaxed); } else { - v.nEnsureCall.fetch_add( 1, atomics::memory_order_relaxed ); + v.nUpdateCall.fetch_add( 1, atomics::memory_order_relaxed ); ++nModified; } } @@ -204,23 +218,31 @@ namespace map2 { { operator()( bNew, val.first, val.second ); } + + // For MultiLevelHashMap + template + void operator()( Val& cur, Val * old ) + { + operator()( old != nullptr, cur.first, cur.second ); + } + private: - ensure_functor(const ensure_functor& ); + update_functor(const update_functor& ) = delete; }; public: - size_t m_nEnsureFailed; - size_t m_nEnsureCreated; - size_t m_nEnsureExisted; + size_t m_nUpdateFailed; + size_t m_nUpdateCreated; + size_t m_nUpdateExisted; size_t m_nFunctorCreated; size_t m_nFunctorModified; public: - Ensurer( CppUnitMini::ThreadPool& pool, Map& rMap ) + Updater( CppUnitMini::ThreadPool& pool, Map& rMap ) : CppUnitMini::TestThread( pool ) , m_Map( rMap ) {} - Ensurer( Ensurer& src ) + Updater( Updater& src ) : CppUnitMini::TestThread( src ) , m_Map( src.m_Map ) {} @@ -237,42 +259,43 @@ namespace map2 { { Map& rMap = m_Map; - m_nEnsureCreated = - m_nEnsureExisted = - m_nEnsureFailed = 0; + m_nUpdateCreated = + m_nUpdateExisted = + m_nUpdateFailed = 0; - ensure_functor func; + update_functor func; key_array const& arr = getTest().m_arrValues; + size_t const nPassCount = getTest().c_nThreadPassCount; if ( m_nThreadNo & 1 ) { - for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { + for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) { for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) { //for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) { - std::pair ret = rMap.ensure( *it, std::ref( func ) ); + std::pair ret = rMap.update( *it, std::ref( func ) ); if ( ret.first ) { if ( ret.second ) - ++m_nEnsureCreated; + ++m_nUpdateCreated; else - ++m_nEnsureExisted; + ++m_nUpdateExisted; } else - ++m_nEnsureFailed; + ++m_nUpdateFailed; } } } else { - for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { + for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) { for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) { - std::pair ret = rMap.ensure( *it, std::ref( func ) ); + std::pair ret = rMap.update( *it, std::ref( func ) ); if ( ret.first ) { if ( ret.second ) - ++m_nEnsureCreated; + ++m_nUpdateCreated; else - ++m_nEnsureExisted; + ++m_nUpdateExisted; } else - ++m_nEnsureFailed; + ++m_nUpdateFailed; } } } @@ -370,9 +393,10 @@ namespace map2 { erase_functor func; key_array const& arr = getTest().m_arrValues; + size_t const nPassCount = getTest().c_nThreadPassCount; if ( m_nThreadNo & 1 ) { - for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { + for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) { for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) { func.m_cnt.nKeyExpected = *it; if ( rMap.erase( *it, std::ref(func) )) @@ -383,7 +407,7 @@ namespace map2 { } } else { - for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { + for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) { for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) { func.m_cnt.nKeyExpected = *it; if ( rMap.erase( *it, std::ref(func) )) @@ -406,7 +430,7 @@ namespace map2 { { typedef Inserter InserterThread; typedef Deleter DeleterThread; - typedef Ensurer EnsurerThread; + typedef Updater UpdaterThread; cds::OS::Timer timer; m_arrValues.clear(); @@ -418,7 +442,7 @@ namespace map2 { CppUnitMini::ThreadPool pool( *this ); pool.add( new InserterThread( pool, testMap ), c_nInsertThreadCount ); pool.add( new DeleterThread( pool, testMap ), c_nDeleteThreadCount ); - pool.add( new EnsurerThread( pool, testMap ), c_nEnsureThreadCount ); + pool.add( new UpdaterThread( pool, testMap ), c_nUpdateThreadCount ); pool.run(); CPPUNIT_MSG( " Duration=" << pool.avgDuration() ); @@ -428,9 +452,9 @@ namespace map2 { size_t nDeleteFailed = 0; size_t nDelValueSuccess = 0; size_t nDelValueFailed = 0; - size_t nEnsureFailed = 0; - size_t nEnsureCreated = 0; - size_t nEnsureModified = 0; + size_t nUpdateFailed = 0; + size_t nUpdateCreated = 0; + size_t nUpdateModified = 0; size_t nEnsFuncCreated = 0; size_t nEnsFuncModified = 0; size_t nTestFunctorRef = 0; @@ -451,10 +475,10 @@ namespace map2 { nDelValueFailed += p->m_nValueFailed; } else { - EnsurerThread * pEns = static_cast( *it ); - nEnsureCreated += pEns->m_nEnsureCreated; - nEnsureModified += pEns->m_nEnsureExisted; - nEnsureFailed += pEns->m_nEnsureFailed; + UpdaterThread * pEns = static_cast( *it ); + nUpdateCreated += pEns->m_nUpdateCreated; + nUpdateModified += pEns->m_nUpdateExisted; + nUpdateFailed += pEns->m_nUpdateFailed; nEnsFuncCreated += pEns->m_nFunctorCreated; nEnsFuncModified += pEns->m_nFunctorModified; } @@ -465,18 +489,18 @@ namespace map2 { << " Del succ=" << nDeleteSuccess << "\n" << " : Ins fail=" << nInsertFailed << " Del fail=" << nDeleteFailed << "\n" - << " : Ensure succ=" << (nEnsureCreated + nEnsureModified) << " fail=" << nEnsureFailed - << " create=" << nEnsureCreated << " modify=" << nEnsureModified << "\n" + << " : Update succ=" << (nUpdateCreated + nUpdateModified) << " fail=" << nUpdateFailed + << " create=" << nUpdateCreated << " modify=" << nUpdateModified << "\n" << " Map size=" << testMap.size() ); CPPUNIT_CHECK_EX( nDelValueFailed == 0, "Functor del failed=" << nDelValueFailed ); CPPUNIT_CHECK_EX( nDelValueSuccess == nDeleteSuccess, "Delete success=" << nDeleteSuccess << " functor=" << nDelValueSuccess ); - CPPUNIT_CHECK( nEnsureFailed == 0 ); + CPPUNIT_CHECK( nUpdateFailed == 0 ); - CPPUNIT_CHECK_EX( nEnsureCreated == nEnsFuncCreated, "Ensure created=" << nEnsureCreated << " functor=" << nEnsFuncCreated ); - CPPUNIT_CHECK_EX( nEnsureModified == nEnsFuncModified, "Ensure modified=" << nEnsureModified << " functor=" << nEnsFuncModified ); + CPPUNIT_CHECK_EX( nUpdateCreated == nEnsFuncCreated, "Update created=" << nUpdateCreated << " functor=" << nEnsFuncCreated ); + CPPUNIT_CHECK_EX( nUpdateModified == nEnsFuncModified, "Update modified=" << nUpdateModified << " functor=" << nEnsFuncModified ); // nTestFunctorRef is call count of insert functor CPPUNIT_CHECK_EX( nTestFunctorRef == nInsertSuccess, "nInsertSuccess=" << nInsertSuccess << " functor nTestFunctorRef=" << nTestFunctorRef ); @@ -497,63 +521,57 @@ namespace map2 { } template - void test() + void run_test() { CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount << " delete=" << c_nDeleteThreadCount - << " ensure=" << c_nEnsureThreadCount + << " update=" << c_nUpdateThreadCount << " pass count=" << c_nThreadPassCount << " map size=" << c_nMapSize ); - for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) { - CPPUNIT_MSG( "Load factor=" << nLoadFactor ); - Map testMap( c_nMapSize, nLoadFactor ); + if ( Map::c_bLoadFactorDepended ) { + for ( size_t c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) { + CPPUNIT_MSG( "Load factor=" << c_nLoadFactor ); + Map testMap( *this ); + do_test( testMap ); + if ( c_bPrintGCState ) + print_gc_state(); + } + } + else { + Map testMap( *this ); do_test( testMap ); if ( c_bPrintGCState ) print_gc_state(); } - - } - - template - void test_nolf() - { - CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount - << " delete=" << c_nDeleteThreadCount - << " ensure=" << c_nEnsureThreadCount - << " pass count=" << c_nThreadPassCount - << " map size=" << c_nMapSize - ); - - Map testMap; - do_test( testMap ); - if ( c_bPrintGCState ) - print_gc_state(); } typedef CppUnitMini::TestCase Base; void setUpParams( const CppUnitMini::TestCfg& cfg ); - void run_MichaelMap(const char *in_name, bool invert = false); - void run_SplitList(const char *in_name, bool invert = false); - void run_StripedMap(const char *in_name, bool invert = false); - void run_RefinableMap(const char *in_name, bool invert = false); - void run_CuckooMap(const char *in_name, bool invert = false); - void run_SkipListMap(const char *in_name, bool invert = false); - void run_EllenBinTreeMap(const char *in_name, bool invert = false); - void run_BronsonAVLTreeMap(const char *in_name, bool invert = false); - - virtual void myRun(const char *in_name, bool invert = false); - # include "map2/map_defs.h" - CDSUNIT_DECLARE_MichaelMap - CDSUNIT_DECLARE_SplitList - CDSUNIT_DECLARE_SkipListMap - CDSUNIT_DECLARE_EllenBinTreeMap - CDSUNIT_DECLARE_BronsonAVLTreeMap - CDSUNIT_DECLARE_StripedMap - CDSUNIT_DECLARE_RefinableMap - CDSUNIT_DECLARE_CuckooMap + CDSUNIT_DECLARE_MichaelMap + CDSUNIT_DECLARE_SplitList + CDSUNIT_DECLARE_SkipListMap + CDSUNIT_DECLARE_EllenBinTreeMap + CDSUNIT_DECLARE_BronsonAVLTreeMap + CDSUNIT_DECLARE_MultiLevelHashMap + CDSUNIT_DECLARE_StripedMap + CDSUNIT_DECLARE_RefinableMap + CDSUNIT_DECLARE_CuckooMap + + CPPUNIT_TEST_SUITE(Map_InsDel_func) + CDSUNIT_TEST_MichaelMap + CDSUNIT_TEST_SplitList + CDSUNIT_TEST_SkipListMap + CDSUNIT_TEST_EllenBinTreeMap + CDSUNIT_TEST_BronsonAVLTreeMap + CDSUNIT_TEST_MultiLevelHashMap + CDSUNIT_TEST_CuckooMap + CDSUNIT_TEST_StripedMap + CDSUNIT_TEST_RefinableMap + CPPUNIT_TEST_SUITE_END(); + }; } // namespace map2 diff --git a/tests/unit/map2/map_insdel_func_bronsonavltree.cpp b/tests/unit/map2/map_insdel_func_bronsonavltree.cpp index 0c03dfc7..585311f7 100644 --- a/tests/unit/map2/map_insdel_func_bronsonavltree.cpp +++ b/tests/unit/map2/map_insdel_func_bronsonavltree.cpp @@ -3,10 +3,10 @@ #include "map2/map_insdel_func.h" #include "map2/map_type_bronson_avltree.h" -namespace map2 { - CDSUNIT_DEFINE_BronsonAVLTreeMap( cc::bronson_avltree::implementation_tag, Map_InsDel_func) +#undef TEST_CASE +#define TEST_CASE(TAG, X) void Map_InsDel_func::X() { run_test::X>(); } +#include "map2/map_defs.h" - CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_BronsonAVLTreeMap ) - CDSUNIT_TEST_BronsonAVLTreeMap - CPPUNIT_TEST_SUITE_END_PART() +namespace map2 { + CDSUNIT_DECLARE_BronsonAVLTreeMap } // namespace map2 diff --git a/tests/unit/map2/map_insdel_func_cuckoo.cpp b/tests/unit/map2/map_insdel_func_cuckoo.cpp index 272e46af..257562f4 100644 --- a/tests/unit/map2/map_insdel_func_cuckoo.cpp +++ b/tests/unit/map2/map_insdel_func_cuckoo.cpp @@ -3,10 +3,10 @@ #include "map2/map_insdel_func.h" #include "map2/map_type_cuckoo.h" -namespace map2 { - CDSUNIT_DEFINE_CuckooMap(cds::intrusive::cuckoo::implementation_tag, Map_InsDel_func) +#undef TEST_CASE +#define TEST_CASE(TAG, X) void Map_InsDel_func::X() { run_test::X>(); } +#include "map2/map_defs.h" - CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_CuckooMap ) - CDSUNIT_TEST_CuckooMap - CPPUNIT_TEST_SUITE_END_PART() +namespace map2 { + CDSUNIT_DECLARE_CuckooMap } // namespace map2 diff --git a/tests/unit/map2/map_insdel_func_ellentree.cpp b/tests/unit/map2/map_insdel_func_ellentree.cpp index 3eca4dc2..450aa441 100644 --- a/tests/unit/map2/map_insdel_func_ellentree.cpp +++ b/tests/unit/map2/map_insdel_func_ellentree.cpp @@ -3,11 +3,10 @@ #include "map2/map_insdel_func.h" #include "map2/map_type_ellen_bintree.h" -namespace map2 { - CDSUNIT_DEFINE_EllenBinTreeMap( cc::ellen_bintree::implementation_tag, Map_InsDel_func) +#undef TEST_CASE +#define TEST_CASE(TAG, X) void Map_InsDel_func::X() { run_test::X>(); } +#include "map2/map_defs.h" - CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_EllenBinTreeMap ) - CDSUNIT_TEST_EllenBinTreeMap - CPPUNIT_TEST_SUITE_END_PART() +namespace map2 { + CDSUNIT_DECLARE_EllenBinTreeMap } // namespace map2 - diff --git a/tests/unit/map2/map_insdel_func_michael.cpp b/tests/unit/map2/map_insdel_func_michael.cpp index 7ef1c982..733c8332 100644 --- a/tests/unit/map2/map_insdel_func_michael.cpp +++ b/tests/unit/map2/map_insdel_func_michael.cpp @@ -3,10 +3,10 @@ #include "map2/map_insdel_func.h" #include "map2/map_type_michael.h" -namespace map2 { - CDSUNIT_DEFINE_MichaelMap( cc::michael_map::implementation_tag, Map_InsDel_func ) +#undef TEST_CASE +#define TEST_CASE(TAG, X) void Map_InsDel_func::X() { run_test::X>(); } +#include "map2/map_defs.h" - CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_MichaelMap ) - CDSUNIT_TEST_MichaelMap - CPPUNIT_TEST_SUITE_END_PART() +namespace map2 { + CDSUNIT_DECLARE_MichaelMap } // namespace map2 diff --git a/tests/unit/map2/map_insdel_func_multilevelhashmap.cpp b/tests/unit/map2/map_insdel_func_multilevelhashmap.cpp new file mode 100644 index 00000000..d215334d --- /dev/null +++ b/tests/unit/map2/map_insdel_func_multilevelhashmap.cpp @@ -0,0 +1,12 @@ +//$$CDS-header$$ + +#include "map2/map_insdel_func.h" +#include "map2/map_type_multilevel_hashmap.h" + +#undef TEST_CASE +#define TEST_CASE(TAG, X) void Map_InsDel_func::X() { run_test::X>(); } +#include "map2/map_defs.h" + +namespace map2 { + CDSUNIT_DECLARE_MultiLevelHashMap +} // namespace map2 diff --git a/tests/unit/map2/map_insdel_func_refinable.cpp b/tests/unit/map2/map_insdel_func_refinable.cpp deleted file mode 100644 index 9203731d..00000000 --- a/tests/unit/map2/map_insdel_func_refinable.cpp +++ /dev/null @@ -1,12 +0,0 @@ -//$$CDS-header$$ - -#include "map2/map_insdel_func.h" -#include "map2/map_type_striped.h" - -namespace map2 { - CDSUNIT_DEFINE_RefinableMap(cc::striped_set::implementation_tag, Map_InsDel_func) - - CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_RefinableMap ) - CDSUNIT_TEST_RefinableMap - CPPUNIT_TEST_SUITE_END_PART() -} // namespace map2 diff --git a/tests/unit/map2/map_insdel_func_skip.cpp b/tests/unit/map2/map_insdel_func_skip.cpp index d0ba0670..106f6bad 100644 --- a/tests/unit/map2/map_insdel_func_skip.cpp +++ b/tests/unit/map2/map_insdel_func_skip.cpp @@ -3,11 +3,10 @@ #include "map2/map_insdel_func.h" #include "map2/map_type_skip_list.h" -namespace map2 { - CDSUNIT_DEFINE_SkipListMap( cc::skip_list::implementation_tag, Map_InsDel_func) +#undef TEST_CASE +#define TEST_CASE(TAG, X) void Map_InsDel_func::X() { run_test::X>(); } +#include "map2/map_defs.h" - CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_SkipListMap ) - CDSUNIT_TEST_SkipListMap - CPPUNIT_TEST_SUITE_END_PART() +namespace map2 { + CDSUNIT_DECLARE_SkipListMap } // namespace map2 - diff --git a/tests/unit/map2/map_insdel_func_split.cpp b/tests/unit/map2/map_insdel_func_split.cpp index d7761456..b6c732fb 100644 --- a/tests/unit/map2/map_insdel_func_split.cpp +++ b/tests/unit/map2/map_insdel_func_split.cpp @@ -3,11 +3,10 @@ #include "map2/map_insdel_func.h" #include "map2/map_type_split_list.h" -namespace map2 { - CDSUNIT_DEFINE_SplitList( cc::split_list::implementation_tag, Map_InsDel_func ) +#undef TEST_CASE +#define TEST_CASE(TAG, X) void Map_InsDel_func::X() { run_test::X>(); } +#include "map2/map_defs.h" - CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_SplitList ) - CDSUNIT_TEST_SplitList - CPPUNIT_TEST_SUITE_END_PART() +namespace map2 { + CDSUNIT_DECLARE_SplitList } // namespace map2 - diff --git a/tests/unit/map2/map_insdel_func_striped.cpp b/tests/unit/map2/map_insdel_func_striped.cpp index 424184ce..b48e8c21 100644 --- a/tests/unit/map2/map_insdel_func_striped.cpp +++ b/tests/unit/map2/map_insdel_func_striped.cpp @@ -3,10 +3,11 @@ #include "map2/map_insdel_func.h" #include "map2/map_type_striped.h" -namespace map2 { - CDSUNIT_DEFINE_StripedMap(cc::striped_set::implementation_tag, Map_InsDel_func) +#undef TEST_CASE +#define TEST_CASE(TAG, X) void Map_InsDel_func::X() { run_test::X>(); } +#include "map2/map_defs.h" - CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_StripedMap ) - CDSUNIT_TEST_StripedMap - CPPUNIT_TEST_SUITE_END_PART() +namespace map2 { + CDSUNIT_DECLARE_StripedMap + CDSUNIT_DECLARE_RefinableMap } // namespace map2 -- 2.34.1