3 #include "cppunit/thread.h"
4 #include "map2/map_type.h"
5 #include <cds/os/topology.h>
9 # define TEST_CASE(TAG, X) void X();
17 key_thread( size_t key, size_t threadNo )
28 struct cmp<key_thread> {
29 int operator ()(key_thread const& k1, key_thread const& k2) const
31 if ( k1.nKey < k2.nKey )
33 if ( k1.nKey > k2.nKey )
35 if ( k1.nThread < k2.nThread )
37 if ( k1.nThread > k2.nThread )
41 int operator ()(key_thread const& k1, size_t k2) const
49 int operator ()(size_t k1, key_thread const& k2) const
63 struct less<map2::key_thread>
65 bool operator()(map2::key_thread const& k1, map2::key_thread const& k2) const
67 if ( k1.nKey <= k2.nKey )
68 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
74 struct hash<map2::key_thread>
76 typedef size_t result_type;
77 typedef map2::key_thread argument_type;
79 size_t operator()( map2::key_thread const& k ) const
81 return std::hash<size_t>()(k.nKey);
83 size_t operator()( size_t k ) const
85 return std::hash<size_t>()(k);
91 inline size_t hash_value( map2::key_thread const& k )
93 return std::hash<size_t>()( k.nKey );
97 struct hash<map2::key_thread>
99 typedef size_t result_type;
100 typedef map2::key_thread argument_type;
102 size_t operator()(map2::key_thread const& k) const
104 return boost::hash<size_t>()( k.nKey );
106 size_t operator()(size_t k) const
108 return boost::hash<size_t>()( k );
115 class Map_DelOdd: public CppUnitMini::TestCase
118 size_t c_nInsThreadCount = 4; // insert thread count
119 size_t c_nDelThreadCount = 4; // delete thread count
120 size_t c_nExtractThreadCount = 4; // extract thread count
121 size_t c_nMapSize = 1000000; // max map size
122 size_t c_nMaxLoadFactor = 8; // maximum load factor
123 size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
124 size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
125 size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
127 bool c_bPrintGCState = true;
129 size_t c_nLoadFactor; // current load factor
132 std::vector<size_t> m_arrInsert;
133 std::vector<size_t> m_arrRemove;
136 typedef CppUnitMini::TestCase Base;
138 typedef key_thread key_type;
139 typedef size_t value_type;
140 typedef std::pair<key_type const, value_type> pair_type;
142 atomics::atomic<size_t> m_nInsThreadCount;
144 // Inserts keys from [0..N)
146 class InsertThread: public CppUnitMini::TestThread
150 virtual InsertThread * clone()
152 return new InsertThread( *this );
157 template <typename Q>
158 void operator()( bool /*bNew*/, Q const& )
160 template <typename Q, typename V>
161 void operator()( bool /*bNew*/, Q const&, V& )
165 template <typename Q>
166 void operator()( Q&, Q*)
170 size_t m_nInsertSuccess;
171 size_t m_nInsertFailed;
174 InsertThread( CppUnitMini::ThreadPool& pool, Map& rMap )
175 : CppUnitMini::TestThread( pool )
178 InsertThread( InsertThread& src )
179 : CppUnitMini::TestThread( src )
183 Map_DelOdd& getTest()
185 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
188 virtual void init() { cds::threading::Manager::attachThread() ; }
189 virtual void fini() { cds::threading::Manager::detachThread() ; }
198 std::vector<size_t>& arrData = getTest().m_arrInsert;
199 for ( size_t i = 0; i < arrData.size(); ++i ) {
200 if ( rMap.insert( key_type( arrData[i], m_nThreadNo )))
207 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
208 if ( arrData[i] & 1 ) {
209 rMap.update( key_type( arrData[i], m_nThreadNo ), f );
213 getTest().m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_acquire );
218 bool operator()( key_type const& k1, key_type const& k2 ) const
220 return k1.nKey == k2.nKey;
222 bool operator()( size_t k1, key_type const& k2 ) const
224 return k1 == k2.nKey;
226 bool operator()( key_type const& k1, size_t k2 ) const
228 return k1.nKey == k2;
233 bool operator()( key_type const& k1, key_type const& k2 ) const
235 return k1.nKey < k2.nKey;
237 bool operator()( size_t k1, key_type const& k2 ) const
241 bool operator()( key_type const& k1, size_t k2 ) const
246 typedef key_equal equal_to;
249 // Deletes odd keys from [0..N)
251 class DeleteThread: public CppUnitMini::TestThread
255 virtual DeleteThread * clone()
257 return new DeleteThread( *this );
260 size_t m_nDeleteSuccess;
261 size_t m_nDeleteFailed;
264 DeleteThread( CppUnitMini::ThreadPool& pool, Map& rMap )
265 : CppUnitMini::TestThread( pool )
268 DeleteThread( DeleteThread& src )
269 : CppUnitMini::TestThread( src )
273 Map_DelOdd& getTest()
275 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
278 virtual void init() { cds::threading::Manager::attachThread() ; }
279 virtual void fini() { cds::threading::Manager::detachThread() ; }
288 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
290 for ( size_t pass = 0; pass < 2; pass++ ) {
291 std::vector<size_t>& arrData = getTest().m_arrRemove;
292 if ( m_nThreadNo & 1 ) {
293 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
294 for ( size_t i = 0; i < arrData.size(); ++i ) {
295 if ( arrData[i] & 1 ) {
296 if ( rMap.erase_with( arrData[i], key_less() ))
302 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
307 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
308 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
309 if ( arrData[i] & 1 ) {
310 if ( rMap.erase_with( arrData[i], key_less() ))
316 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
324 // Deletes odd keys from [0..N)
325 template <class GC, class Map >
326 class ExtractThread: public CppUnitMini::TestThread
330 virtual ExtractThread * clone()
332 return new ExtractThread( *this );
335 size_t m_nDeleteSuccess;
336 size_t m_nDeleteFailed;
339 ExtractThread( CppUnitMini::ThreadPool& pool, Map& rMap )
340 : CppUnitMini::TestThread( pool )
343 ExtractThread( ExtractThread& src )
344 : CppUnitMini::TestThread( src )
348 Map_DelOdd& getTest()
350 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
353 virtual void init() { cds::threading::Manager::attachThread() ; }
354 virtual void fini() { cds::threading::Manager::detachThread() ; }
363 typename Map::guarded_ptr gp;
364 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
366 for ( size_t pass = 0; pass < 2; ++pass ) {
367 std::vector<size_t>& arrData = getTest().m_arrRemove;
368 if ( m_nThreadNo & 1 ) {
369 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
370 for ( size_t i = 0; i < arrData.size(); ++i ) {
371 if ( arrData[i] & 1 ) {
372 gp = rMap.extract_with( arrData[i], key_less());
380 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
385 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
386 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
387 if ( arrData[i] & 1 ) {
388 gp = rMap.extract_with( arrData[i], key_less());
396 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
404 template <class RCU, class Map >
405 class ExtractThread< cds::urcu::gc<RCU>, Map > : public CppUnitMini::TestThread
409 virtual ExtractThread * clone()
411 return new ExtractThread( *this );
414 size_t m_nDeleteSuccess;
415 size_t m_nDeleteFailed;
418 ExtractThread( CppUnitMini::ThreadPool& pool, Map& rMap )
419 : CppUnitMini::TestThread( pool )
422 ExtractThread( ExtractThread& src )
423 : CppUnitMini::TestThread( src )
427 Map_DelOdd& getTest()
429 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
432 virtual void init() { cds::threading::Manager::attachThread() ; }
433 virtual void fini() { cds::threading::Manager::detachThread() ; }
442 typename Map::exempt_ptr xp;
443 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
445 std::vector<size_t>& arrData = getTest().m_arrRemove;
446 if ( m_nThreadNo & 1 ) {
447 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
448 for ( size_t i = 0; i < arrData.size(); ++i ) {
449 if ( arrData[i] & 1 ) {
450 if ( Map::c_bExtractLockExternal ) {
452 typename Map::rcu_lock l;
453 xp = rMap.extract_with( arrData[i], key_less() );
461 xp = rMap.extract_with( arrData[i], key_less() );
470 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
475 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
476 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
477 if ( arrData[i] & 1 ) {
478 if ( Map::c_bExtractLockExternal ) {
480 typename Map::rcu_lock l;
481 xp = rMap.extract_with( arrData[i], key_less() );
489 xp = rMap.extract_with( arrData[i], key_less() );
498 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
509 Map testMap( *this );
510 do_test_with( testMap );
514 void do_test_extract()
516 Map testMap( *this );
517 do_test_extract_with( testMap );
521 void do_test_with( Map& testMap )
523 typedef InsertThread<Map> insert_thread;
524 typedef DeleteThread<Map> delete_thread;
526 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
528 CppUnitMini::ThreadPool pool( *this );
529 pool.add( new insert_thread( pool, testMap ), c_nInsThreadCount );
530 pool.add( new delete_thread( pool, testMap ), c_nDelThreadCount ? c_nDelThreadCount : cds::OS::topology::processor_count());
532 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
534 size_t nInsertSuccess = 0;
535 size_t nInsertFailed = 0;
536 size_t nDeleteSuccess = 0;
537 size_t nDeleteFailed = 0;
538 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
539 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
541 nInsertSuccess += pThread->m_nInsertSuccess;
542 nInsertFailed += pThread->m_nInsertFailed;
545 delete_thread * p = static_cast<delete_thread *>( *it );
546 nDeleteSuccess += p->m_nDeleteSuccess;
547 nDeleteFailed += p->m_nDeleteFailed;
551 CPPUNIT_MSG( " Totals (success/failed): \n\t"
552 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
553 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
555 CPPUNIT_CHECK( nInsertSuccess == c_nMapSize * c_nInsThreadCount );
556 CPPUNIT_CHECK( nInsertFailed == 0 );
562 void do_test_extract_with( Map& testMap )
564 typedef InsertThread<Map> insert_thread;
565 typedef DeleteThread<Map> delete_thread;
566 typedef ExtractThread< typename Map::gc, Map > extract_thread;
568 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
570 CppUnitMini::ThreadPool pool( *this );
571 pool.add( new insert_thread( pool, testMap ), c_nInsThreadCount );
572 if ( c_nDelThreadCount )
573 pool.add( new delete_thread( pool, testMap ), c_nDelThreadCount );
574 if ( c_nExtractThreadCount )
575 pool.add( new extract_thread( pool, testMap ), c_nExtractThreadCount );
577 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
579 size_t nInsertSuccess = 0;
580 size_t nInsertFailed = 0;
581 size_t nDeleteSuccess = 0;
582 size_t nDeleteFailed = 0;
583 size_t nExtractSuccess = 0;
584 size_t nExtractFailed = 0;
585 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
586 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
588 nInsertSuccess += pThread->m_nInsertSuccess;
589 nInsertFailed += pThread->m_nInsertFailed;
592 delete_thread * p = dynamic_cast<delete_thread *>( *it );
594 nDeleteSuccess += p->m_nDeleteSuccess;
595 nDeleteFailed += p->m_nDeleteFailed;
598 extract_thread * pExtract = dynamic_cast<extract_thread *>( *it );
600 nExtractSuccess += pExtract->m_nDeleteSuccess;
601 nExtractFailed += pExtract->m_nDeleteFailed;
606 CPPUNIT_MSG( " Totals (success/failed): \n\t"
607 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
608 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
609 << " Extract=" << nExtractSuccess << '/' << nExtractFailed << "\n\t"
611 CPPUNIT_CHECK( nInsertSuccess == c_nMapSize * c_nInsThreadCount );
612 CPPUNIT_CHECK( nInsertFailed == 0 );
618 void analyze( Map& testMap )
620 cds::OS::Timer timer;
622 // All even keys must be in the map
624 size_t nErrorCount = 0;
625 CPPUNIT_MSG( " Check even keys..." );
626 for ( size_t n = 0; n < c_nMapSize; n +=2 ) {
627 for ( size_t i = 0; i < c_nInsThreadCount; ++i ) {
628 if ( !testMap.contains( key_type(n, i) ) ) {
629 if ( ++nErrorCount < 10 ) {
630 CPPUNIT_MSG( "key " << n << "-" << i << " is not found!");
635 CPPUNIT_CHECK_EX( nErrorCount == 0, "Totals: " << nErrorCount << " keys is not found");
638 check_before_cleanup( testMap );
640 CPPUNIT_MSG( " Clear map (single-threaded)..." );
643 CPPUNIT_MSG( " Duration=" << timer.duration() );
644 CPPUNIT_CHECK_EX( testMap.empty(), ((long long) testMap.size()) );
646 additional_check( testMap );
647 print_stat( testMap );
649 additional_cleanup( testMap );
655 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
657 CPPUNIT_MSG( "Thread count: insert=" << c_nInsThreadCount
658 << ", delete=" << c_nDelThreadCount
659 << ", extract=" << c_nExtractThreadCount
660 << "; set size=" << c_nMapSize
662 if ( Map::c_bLoadFactorDepended ) {
663 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
664 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
665 do_test_extract<Map>();
666 if ( c_bPrintGCState )
671 do_test_extract<Map>();
675 void run_test_no_extract()
677 static_assert( !Map::c_bExtractSupported, "Map class must not support extract() method" );
679 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
680 << " delete thread count=" << c_nDelThreadCount
681 << " set size=" << c_nMapSize
683 if ( Map::c_bLoadFactorDepended ) {
684 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
685 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
687 if ( c_bPrintGCState )
695 void setUpParams( const CppUnitMini::TestCfg& cfg );
697 # include "map2/map_defs.h"
698 CDSUNIT_DECLARE_MichaelMap
699 CDSUNIT_DECLARE_SplitList
700 CDSUNIT_DECLARE_SkipListMap
701 CDSUNIT_DECLARE_EllenBinTreeMap
702 CDSUNIT_DECLARE_BronsonAVLTreeMap
703 CDSUNIT_DECLARE_CuckooMap
705 // This test is not suitable for MultiLevelHashMap
706 //CDSUNIT_DECLARE_MultiLevelHashMap
708 CPPUNIT_TEST_SUITE(Map_DelOdd)
709 CDSUNIT_TEST_MichaelMap
710 CDSUNIT_TEST_SplitList
711 CDSUNIT_TEST_SkipListMap
712 CDSUNIT_TEST_EllenBinTreeMap
713 CDSUNIT_TEST_BronsonAVLTreeMap
714 CDSUNIT_TEST_CuckooMap
716 //CDSUNIT_TEST_MultiLevelHashMap // the test is not suitable
717 CPPUNIT_TEST_SUITE_END();
719 ////CDSUNIT_DECLARE_StripedMap
720 ////CDSUNIT_DECLARE_RefinableMap
721 ////CDSUNIT_DECLARE_StdMap