namespace map2 {
-//# define TEST_MAP(IMPL, C, X) void C::X() { test<map_type<IMPL, key_type, value_type>::X >(); }
-//# define TEST_MAP_DEFAULT_CONSTRUCTIBLE(IMPL, C, X) void C::X() { test_default_constructible<map_type<IMPL, key_type, value_type>::X >(); }
-//# define TEST_MAP_EXTRACT(IMPL, C, X) void C::X() { test_extract<map_type<IMPL, key_type, value_type>::X >(); }
-//# define TEST_MAP_NOLF(IMPL, C, X) void C::X() { test_nolf<map_type<IMPL, key_type, value_type>::X >(); }
-//# define TEST_MAP_NOLF_EXTRACT(IMPL, C, X) void C::X() { test_nolf_extract<map_type<IMPL, key_type, value_type>::X >(); }
-
# define TEST_CASE(TAG, X) void X();
namespace {
size_t c_nExtractThreadCount = 4; // extract thread count
size_t c_nMapSize = 1000000; // max map size
size_t c_nMaxLoadFactor = 8; // maximum load factor
- size_t c_nMultiLevelMap_HeadBits = 10; // for MultiLevelHashMap - log2(size of head array)
- size_t c_nMultiLevelMap_ArrayBits = 8; // for MultiLevelHashMap - log2(size of array node)
+
+ 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 (0 - use default)
+
+ size_t c_nMultiLevelMap_HeadBits = 10;
+ size_t c_nMultiLevelMap_ArrayBits = 4;
bool c_bPrintGCState = true;
std::vector<size_t> m_arrRemove;
protected:
- typedef CppUnitMini::TestCase Base;
-
typedef key_thread key_type;
typedef size_t value_type;
typedef std::pair<key_type const, value_type> pair_type;
virtual void init() { cds::threading::Manager::attachThread() ; }
virtual void fini() { cds::threading::Manager::detachThread() ; }
+ template <typename MapType, bool>
+ struct eraser {
+ static bool erase(MapType& map, size_t key, size_t /*insThread*/)
+ {
+ return map.erase_with(key, key_less());
+ }
+ };
+
+ template <typename MapType>
+ struct eraser<MapType, true>
+ {
+ static bool erase(MapType& map, size_t key, size_t insThread)
+ {
+ return map.erase(key_type(key, insThread));
+ }
+ };
+
virtual void test()
{
Map& rMap = m_Map;
for ( size_t k = 0; k < nInsThreadCount; ++k ) {
for ( size_t i = 0; i < arrData.size(); ++i ) {
if ( arrData[i] & 1 ) {
- if ( rMap.erase_with( arrData[i], key_less() ))
- ++m_nDeleteSuccess;
- else
- ++m_nDeleteFailed;
+ if ( Map::c_bEraseExactKey ) {
+ for (size_t key = 0; key < nInsThreadCount; ++key) {
+ if ( eraser<Map, Map::c_bEraseExactKey>::erase( rMap, arrData[i], key ))
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ }
+ else {
+ if ( eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], 0) )
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
}
}
if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
for ( size_t k = 0; k < nInsThreadCount; ++k ) {
for ( size_t i = arrData.size() - 1; i > 0; --i ) {
if ( arrData[i] & 1 ) {
- if ( rMap.erase_with( arrData[i], key_less() ))
- ++m_nDeleteSuccess;
- else
- ++m_nDeleteFailed;
+ if ( Map::c_bEraseExactKey ) {
+ for (size_t key = 0; key < nInsThreadCount; ++key) {
+ if (eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], key))
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ }
+ else {
+ if (eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], 0))
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
}
}
if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
virtual void init() { cds::threading::Manager::attachThread() ; }
virtual void fini() { cds::threading::Manager::detachThread() ; }
+ template <typename MapType, bool>
+ struct extractor {
+ static typename Map::guarded_ptr extract(MapType& map, size_t key, size_t /*insThread*/)
+ {
+ return map.extract_with(key, key_less());
+ }
+ };
+
+ template <typename MapType>
+ struct extractor<MapType, true>
+ {
+ static typename Map::guarded_ptr extract(MapType& map, size_t key, size_t insThread)
+ {
+ return map.extract(key_type(key, insThread));
+ }
+ };
+
virtual void test()
{
Map& rMap = m_Map;
for ( size_t k = 0; k < nInsThreadCount; ++k ) {
for ( size_t i = 0; i < arrData.size(); ++i ) {
if ( arrData[i] & 1 ) {
- gp = rMap.extract_with( arrData[i], key_less());
+ gp = extractor< Map, Map::c_bEraseExactKey >::extract( rMap, arrData[i], k );
if ( gp )
++m_nDeleteSuccess;
else
for ( size_t k = 0; k < nInsThreadCount; ++k ) {
for ( size_t i = arrData.size() - 1; i > 0; --i ) {
if ( arrData[i] & 1 ) {
- gp = rMap.extract_with( arrData[i], key_less());
+ gp = extractor< Map, Map::c_bEraseExactKey >::extract( rMap, arrData[i], k);
if ( gp )
++m_nDeleteSuccess;
else
virtual void init() { cds::threading::Manager::attachThread() ; }
virtual void fini() { cds::threading::Manager::detachThread() ; }
+ template <typename MapType, bool>
+ struct extractor {
+ static typename Map::exempt_ptr extract( MapType& map, size_t key, size_t /*insThread*/ )
+ {
+ return map.extract_with( key, key_less());
+ }
+ };
+
+ template <typename MapType>
+ struct extractor<MapType, true>
+ {
+ static typename Map::exempt_ptr extract(MapType& map, size_t key, size_t insThread)
+ {
+ return map.extract( key_type(key, insThread));
+ }
+ };
+
virtual void test()
{
Map& rMap = m_Map;
if ( Map::c_bExtractLockExternal ) {
{
typename Map::rcu_lock l;
- xp = rMap.extract_with( arrData[i], key_less() );
+ xp = extractor<Map, Map::c_bEraseExactKey>::extract( rMap, arrData[i], k );
if ( xp )
++m_nDeleteSuccess;
else
}
}
else {
- xp = rMap.extract_with( arrData[i], key_less() );
+ xp = extractor<Map, Map::c_bEraseExactKey>::extract( rMap, arrData[i], k);
if ( xp )
++m_nDeleteSuccess;
else
if ( Map::c_bExtractLockExternal ) {
{
typename Map::rcu_lock l;
- xp = rMap.extract_with( arrData[i], key_less() );
+ xp = extractor<Map, Map::c_bEraseExactKey>::extract(rMap, arrData[i], k);
if ( xp )
++m_nDeleteSuccess;
else
}
}
else {
- xp = rMap.extract_with( arrData[i], key_less() );
+ xp = extractor<Map, Map::c_bEraseExactKey>::extract(rMap, arrData[i], k);
if ( xp )
++m_nDeleteSuccess;
else
additional_cleanup( testMap );
}
- //template <class Map>
- //void test()
- //{
- // CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
- // << " delete thread count=" << c_nDelThreadCount
- // << " set size=" << c_nMapSize
- // );
-
- // for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
- // CPPUNIT_MSG( "Load factor=" << nLoadFactor );
- // do_test<Map>( nLoadFactor );
- // if ( c_bPrintGCState )
- // print_gc_state();
- // }
- //}
-
- //template <class Map>
- //void test_extract()
- //{
- // CPPUNIT_MSG( "Thread count: insert=" << c_nInsThreadCount
- // << ", delete=" << c_nDelThreadCount
- // << ", extract=" << c_nExtractThreadCount
- // << "; set size=" << c_nMapSize
- // );
-
- // for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
- // CPPUNIT_MSG( "Load factor=" << nLoadFactor );
- // do_test_extract<Map>( nLoadFactor );
- // if ( c_bPrintGCState )
- // print_gc_state();
- // }
- //}
-
- //template <class Map>
- //void test_nolf()
- //{
- // CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
- // << " delete thread count=" << c_nDelThreadCount
- // << " set size=" << c_nMapSize
- // );
-
- // Map s;
- // do_test_with( s );
- // if ( c_bPrintGCState )
- // print_gc_state();
- //}
-
- //template <class Map>
- //void test_nolf_extract()
- //{
- // CPPUNIT_MSG( "Thread count: insert=" << c_nInsThreadCount
- // << ", delete=" << c_nDelThreadCount
- // << ", extract=" << c_nExtractThreadCount
- // << "; set size=" << c_nMapSize
- // );
-
- // Map s;
- // do_test_extract_with( s );
- // if ( c_bPrintGCState )
- // print_gc_state();
- //}
-
template <class Map>
void run_test()
{
- if ( Map::c_bExtractSupported ) {
- CPPUNIT_MSG( "Thread count: insert=" << c_nInsThreadCount
- << ", delete=" << c_nDelThreadCount
- << ", extract=" << c_nExtractThreadCount
- << "; set size=" << c_nMapSize
- );
- if ( Map::c_bLoadFactorDepended ) {
- for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
- CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
- do_test_extract<Map>();
- if ( c_bPrintGCState )
- print_gc_state();
- }
- }
- else
+ static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
+
+ CPPUNIT_MSG( "Thread count: insert=" << c_nInsThreadCount
+ << ", delete=" << c_nDelThreadCount
+ << ", extract=" << c_nExtractThreadCount
+ << "; set size=" << c_nMapSize
+ );
+ if ( Map::c_bLoadFactorDepended ) {
+ for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
+ CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
do_test_extract<Map>();
- }
- else {
- CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
- << " delete thread count=" << c_nDelThreadCount
- << " set size=" << c_nMapSize
- );
- if ( Map::c_bLoadFactorDepended ) {
- for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
- CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
- do_test<Map>();
- if ( c_bPrintGCState )
- print_gc_state();
- }
+ if ( c_bPrintGCState )
+ print_gc_state();
}
- else
- do_test<Map>();
}
+ else
+ do_test_extract<Map>();
}
- void setUpParams( const CppUnitMini::TestCfg& cfg );
+ template <class Map>
+ void run_test_no_extract()
+ {
+ static_assert( !Map::c_bExtractSupported, "Map class must not support extract() method" );
- //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);
- //void run_MultiLevelHashMap(const char *in_name, bool invert = false);
- ////void run_StdMap(const char *in_name, bool invert = false);
+ CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
+ << " delete thread count=" << c_nDelThreadCount
+ << " set size=" << c_nMapSize
+ );
+ if ( Map::c_bLoadFactorDepended ) {
+ for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
+ CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
+ do_test<Map>();
+ if ( c_bPrintGCState )
+ print_gc_state();
+ }
+ }
+ else
+ do_test<Map>();
+ }
- //virtual void myRun(const char *in_name, bool invert = false);
+ void setUpParams( const CppUnitMini::TestCfg& cfg );
# include "map2/map_defs.h"
CDSUNIT_DECLARE_MichaelMap
- CDSUNIT_DECLARE_MultiLevelHashMap
+ CDSUNIT_DECLARE_SplitList
+ CDSUNIT_DECLARE_SkipListMap
+ CDSUNIT_DECLARE_EllenBinTreeMap
+ CDSUNIT_DECLARE_BronsonAVLTreeMap
+ CDSUNIT_DECLARE_MultiLevelHashMap_fixed
+ CDSUNIT_DECLARE_MultiLevelHashMap_city
+ CDSUNIT_DECLARE_CuckooMap
CPPUNIT_TEST_SUITE(Map_DelOdd)
CDSUNIT_TEST_MichaelMap
- //CDSUNIT_TEST_MultiLevelHashMap
+ CDSUNIT_TEST_SplitList
+ CDSUNIT_TEST_SkipListMap
+ CDSUNIT_TEST_EllenBinTreeMap
+ CDSUNIT_TEST_BronsonAVLTreeMap
+ CDSUNIT_TEST_MultiLevelHashMap_fixed
+ CDSUNIT_TEST_MultiLevelHashMap_city
+ CDSUNIT_TEST_CuckooMap
CPPUNIT_TEST_SUITE_END();
- //CDSUNIT_DECLARE_MichaelMap
- //CDSUNIT_DECLARE_SplitList
+ // Not implemented yet
////CDSUNIT_DECLARE_StripedMap
////CDSUNIT_DECLARE_RefinableMap
- //CDSUNIT_DECLARE_CuckooMap
- //CDSUNIT_DECLARE_SkipListMap
- //CDSUNIT_DECLARE_EllenBinTreeMap
- //CDSUNIT_DECLARE_BronsonAVLTreeMap
- //CDSUNIT_DECLARE_MultiLevelHashMap
////CDSUNIT_DECLARE_StdMap
};
} // namespace map2
projects / libcds.git / blobdiff