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
124 size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
125 size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
126 size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (0 - use default)
128 size_t c_nFeldmanMap_HeadBits = 10;
129 size_t c_nFeldmanMap_ArrayBits = 4;
131 bool c_bPrintGCState = true;
133 size_t c_nLoadFactor; // current load factor
136 std::vector<size_t> m_arrInsert;
137 std::vector<size_t> m_arrRemove;
140 typedef key_thread key_type;
141 typedef size_t value_type;
142 typedef std::pair<key_type const, value_type> pair_type;
144 atomics::atomic<size_t> m_nInsThreadCount;
146 // Inserts keys from [0..N)
148 class InsertThread: public CppUnitMini::TestThread
152 virtual InsertThread * clone()
154 return new InsertThread( *this );
159 template <typename Q>
160 void operator()( bool /*bNew*/, Q const& )
162 template <typename Q, typename V>
163 void operator()( bool /*bNew*/, Q const&, V& )
167 template <typename Q>
168 void operator()( Q&, Q*)
172 size_t m_nInsertSuccess;
173 size_t m_nInsertFailed;
176 InsertThread( CppUnitMini::ThreadPool& pool, Map& rMap )
177 : CppUnitMini::TestThread( pool )
180 InsertThread( InsertThread& src )
181 : CppUnitMini::TestThread( src )
185 Map_DelOdd& getTest()
187 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
190 virtual void init() { cds::threading::Manager::attachThread() ; }
191 virtual void fini() { cds::threading::Manager::detachThread() ; }
200 std::vector<size_t>& arrData = getTest().m_arrInsert;
201 for ( size_t i = 0; i < arrData.size(); ++i ) {
202 if ( rMap.insert( key_type( arrData[i], m_nThreadNo )))
209 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
210 if ( arrData[i] & 1 ) {
211 rMap.update( key_type( arrData[i], m_nThreadNo ), f );
215 getTest().m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_acquire );
220 bool operator()( key_type const& k1, key_type const& k2 ) const
222 return k1.nKey == k2.nKey;
224 bool operator()( size_t k1, key_type const& k2 ) const
226 return k1 == k2.nKey;
228 bool operator()( key_type const& k1, size_t k2 ) const
230 return k1.nKey == k2;
235 bool operator()( key_type const& k1, key_type const& k2 ) const
237 return k1.nKey < k2.nKey;
239 bool operator()( size_t k1, key_type const& k2 ) const
243 bool operator()( key_type const& k1, size_t k2 ) const
248 typedef key_equal equal_to;
251 // Deletes odd keys from [0..N)
253 class DeleteThread: public CppUnitMini::TestThread
257 virtual DeleteThread * clone()
259 return new DeleteThread( *this );
262 size_t m_nDeleteSuccess;
263 size_t m_nDeleteFailed;
266 DeleteThread( CppUnitMini::ThreadPool& pool, Map& rMap )
267 : CppUnitMini::TestThread( pool )
270 DeleteThread( DeleteThread& src )
271 : CppUnitMini::TestThread( src )
275 Map_DelOdd& getTest()
277 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
280 virtual void init() { cds::threading::Manager::attachThread() ; }
281 virtual void fini() { cds::threading::Manager::detachThread() ; }
283 template <typename MapType, bool>
285 static bool erase(MapType& map, size_t key, size_t /*insThread*/)
287 return map.erase_with(key, key_less());
291 template <typename MapType>
292 struct eraser<MapType, true>
294 static bool erase(MapType& map, size_t key, size_t insThread)
296 return map.erase(key_type(key, insThread));
307 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
309 for ( size_t pass = 0; pass < 2; pass++ ) {
310 std::vector<size_t>& arrData = getTest().m_arrRemove;
311 if ( m_nThreadNo & 1 ) {
312 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
313 for ( size_t i = 0; i < arrData.size(); ++i ) {
314 if ( arrData[i] & 1 ) {
315 if ( Map::c_bEraseExactKey ) {
316 for (size_t key = 0; key < nInsThreadCount; ++key) {
317 if ( eraser<Map, Map::c_bEraseExactKey>::erase( rMap, arrData[i], key ))
324 if ( eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], 0) )
331 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
336 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
337 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
338 if ( arrData[i] & 1 ) {
339 if ( Map::c_bEraseExactKey ) {
340 for (size_t key = 0; key < nInsThreadCount; ++key) {
341 if (eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], key))
348 if (eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], 0))
355 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
363 // Deletes odd keys from [0..N)
364 template <class GC, class Map >
365 class ExtractThread: public CppUnitMini::TestThread
369 virtual ExtractThread * clone()
371 return new ExtractThread( *this );
374 size_t m_nDeleteSuccess;
375 size_t m_nDeleteFailed;
378 ExtractThread( CppUnitMini::ThreadPool& pool, Map& rMap )
379 : CppUnitMini::TestThread( pool )
382 ExtractThread( ExtractThread& src )
383 : CppUnitMini::TestThread( src )
387 Map_DelOdd& getTest()
389 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
392 virtual void init() { cds::threading::Manager::attachThread() ; }
393 virtual void fini() { cds::threading::Manager::detachThread() ; }
395 template <typename MapType, bool>
397 static typename Map::guarded_ptr extract(MapType& map, size_t key, size_t /*insThread*/)
399 return map.extract_with(key, key_less());
403 template <typename MapType>
404 struct extractor<MapType, true>
406 static typename Map::guarded_ptr extract(MapType& map, size_t key, size_t insThread)
408 return map.extract(key_type(key, insThread));
419 typename Map::guarded_ptr gp;
420 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
422 for ( size_t pass = 0; pass < 2; ++pass ) {
423 std::vector<size_t>& arrData = getTest().m_arrRemove;
424 if ( m_nThreadNo & 1 ) {
425 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
426 for ( size_t i = 0; i < arrData.size(); ++i ) {
427 if ( arrData[i] & 1 ) {
428 gp = extractor< Map, Map::c_bEraseExactKey >::extract( rMap, arrData[i], k );
436 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
441 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
442 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
443 if ( arrData[i] & 1 ) {
444 gp = extractor< Map, Map::c_bEraseExactKey >::extract( rMap, arrData[i], k);
452 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
460 template <class RCU, class Map >
461 class ExtractThread< cds::urcu::gc<RCU>, Map > : public CppUnitMini::TestThread
465 virtual ExtractThread * clone()
467 return new ExtractThread( *this );
470 size_t m_nDeleteSuccess;
471 size_t m_nDeleteFailed;
474 ExtractThread( CppUnitMini::ThreadPool& pool, Map& rMap )
475 : CppUnitMini::TestThread( pool )
478 ExtractThread( ExtractThread& src )
479 : CppUnitMini::TestThread( src )
483 Map_DelOdd& getTest()
485 return reinterpret_cast<Map_DelOdd&>( m_Pool.m_Test );
488 virtual void init() { cds::threading::Manager::attachThread() ; }
489 virtual void fini() { cds::threading::Manager::detachThread() ; }
491 template <typename MapType, bool>
493 static typename Map::exempt_ptr extract( MapType& map, size_t key, size_t /*insThread*/ )
495 return map.extract_with( key, key_less());
499 template <typename MapType>
500 struct extractor<MapType, true>
502 static typename Map::exempt_ptr extract(MapType& map, size_t key, size_t insThread)
504 return map.extract( key_type(key, insThread));
515 typename Map::exempt_ptr xp;
516 size_t const nInsThreadCount = getTest().c_nInsThreadCount;
518 std::vector<size_t>& arrData = getTest().m_arrRemove;
519 if ( m_nThreadNo & 1 ) {
520 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
521 for ( size_t i = 0; i < arrData.size(); ++i ) {
522 if ( arrData[i] & 1 ) {
523 if ( Map::c_bExtractLockExternal ) {
525 typename Map::rcu_lock l;
526 xp = extractor<Map, Map::c_bEraseExactKey>::extract( rMap, arrData[i], k );
534 xp = extractor<Map, Map::c_bEraseExactKey>::extract( rMap, arrData[i], k);
543 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
548 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
549 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
550 if ( arrData[i] & 1 ) {
551 if ( Map::c_bExtractLockExternal ) {
553 typename Map::rcu_lock l;
554 xp = extractor<Map, Map::c_bEraseExactKey>::extract(rMap, arrData[i], k);
562 xp = extractor<Map, Map::c_bEraseExactKey>::extract(rMap, arrData[i], k);
571 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
582 Map testMap( *this );
583 do_test_with( testMap );
587 void do_test_extract()
589 Map testMap( *this );
590 do_test_extract_with( testMap );
594 void do_test_with( Map& testMap )
596 typedef InsertThread<Map> insert_thread;
597 typedef DeleteThread<Map> delete_thread;
599 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
601 CppUnitMini::ThreadPool pool( *this );
602 pool.add( new insert_thread( pool, testMap ), c_nInsThreadCount );
603 pool.add( new delete_thread( pool, testMap ), c_nDelThreadCount ? c_nDelThreadCount : cds::OS::topology::processor_count());
605 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
607 size_t nInsertSuccess = 0;
608 size_t nInsertFailed = 0;
609 size_t nDeleteSuccess = 0;
610 size_t nDeleteFailed = 0;
611 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
612 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
614 nInsertSuccess += pThread->m_nInsertSuccess;
615 nInsertFailed += pThread->m_nInsertFailed;
618 delete_thread * p = static_cast<delete_thread *>( *it );
619 nDeleteSuccess += p->m_nDeleteSuccess;
620 nDeleteFailed += p->m_nDeleteFailed;
624 CPPUNIT_MSG( " Totals (success/failed): \n\t"
625 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
626 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
628 CPPUNIT_CHECK( nInsertSuccess == c_nMapSize * c_nInsThreadCount );
629 CPPUNIT_CHECK( nInsertFailed == 0 );
635 void do_test_extract_with( Map& testMap )
637 typedef InsertThread<Map> insert_thread;
638 typedef DeleteThread<Map> delete_thread;
639 typedef ExtractThread< typename Map::gc, Map > extract_thread;
641 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
643 CppUnitMini::ThreadPool pool( *this );
644 pool.add( new insert_thread( pool, testMap ), c_nInsThreadCount );
645 if ( c_nDelThreadCount )
646 pool.add( new delete_thread( pool, testMap ), c_nDelThreadCount );
647 if ( c_nExtractThreadCount )
648 pool.add( new extract_thread( pool, testMap ), c_nExtractThreadCount );
650 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
652 size_t nInsertSuccess = 0;
653 size_t nInsertFailed = 0;
654 size_t nDeleteSuccess = 0;
655 size_t nDeleteFailed = 0;
656 size_t nExtractSuccess = 0;
657 size_t nExtractFailed = 0;
658 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
659 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
661 nInsertSuccess += pThread->m_nInsertSuccess;
662 nInsertFailed += pThread->m_nInsertFailed;
665 delete_thread * p = dynamic_cast<delete_thread *>( *it );
667 nDeleteSuccess += p->m_nDeleteSuccess;
668 nDeleteFailed += p->m_nDeleteFailed;
671 extract_thread * pExtract = dynamic_cast<extract_thread *>( *it );
673 nExtractSuccess += pExtract->m_nDeleteSuccess;
674 nExtractFailed += pExtract->m_nDeleteFailed;
679 CPPUNIT_MSG( " Totals (success/failed): \n\t"
680 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
681 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
682 << " Extract=" << nExtractSuccess << '/' << nExtractFailed << "\n\t"
684 CPPUNIT_CHECK( nInsertSuccess == c_nMapSize * c_nInsThreadCount );
685 CPPUNIT_CHECK( nInsertFailed == 0 );
691 void analyze( Map& testMap )
693 cds::OS::Timer timer;
695 // All even keys must be in the map
697 size_t nErrorCount = 0;
698 CPPUNIT_MSG( " Check even keys..." );
699 for ( size_t n = 0; n < c_nMapSize; n +=2 ) {
700 for ( size_t i = 0; i < c_nInsThreadCount; ++i ) {
701 if ( !testMap.contains( key_type(n, i) ) ) {
702 if ( ++nErrorCount < 10 ) {
703 CPPUNIT_MSG( "key " << n << "-" << i << " is not found!");
708 CPPUNIT_CHECK_EX( nErrorCount == 0, "Totals: " << nErrorCount << " keys is not found");
711 check_before_cleanup( testMap );
713 CPPUNIT_MSG( " Clear map (single-threaded)..." );
716 CPPUNIT_MSG( " Duration=" << timer.duration() );
717 CPPUNIT_CHECK_EX( testMap.empty(), ((long long) testMap.size()) );
719 additional_check( testMap );
720 print_stat( testMap );
722 additional_cleanup( testMap );
728 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
730 CPPUNIT_MSG( "Thread count: insert=" << c_nInsThreadCount
731 << ", delete=" << c_nDelThreadCount
732 << ", extract=" << c_nExtractThreadCount
733 << "; set size=" << c_nMapSize
735 if ( Map::c_bLoadFactorDepended ) {
736 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
737 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
738 do_test_extract<Map>();
739 if ( c_bPrintGCState )
744 do_test_extract<Map>();
748 void run_test_no_extract()
750 static_assert( !Map::c_bExtractSupported, "Map class must not support extract() method" );
752 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
753 << " delete thread count=" << c_nDelThreadCount
754 << " set size=" << c_nMapSize
756 if ( Map::c_bLoadFactorDepended ) {
757 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
758 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
760 if ( c_bPrintGCState )
768 void setUpParams( const CppUnitMini::TestCfg& cfg );
770 # include "map2/map_defs.h"
771 CDSUNIT_DECLARE_MichaelMap
772 CDSUNIT_DECLARE_SplitList
773 CDSUNIT_DECLARE_SkipListMap
774 CDSUNIT_DECLARE_EllenBinTreeMap
775 CDSUNIT_DECLARE_BronsonAVLTreeMap
776 CDSUNIT_DECLARE_FeldmanHashMap_fixed
777 CDSUNIT_DECLARE_FeldmanHashMap_city
778 CDSUNIT_DECLARE_CuckooMap
780 CPPUNIT_TEST_SUITE(Map_DelOdd)
781 CDSUNIT_TEST_MichaelMap
782 CDSUNIT_TEST_SplitList
783 CDSUNIT_TEST_SkipListMap
784 CDSUNIT_TEST_EllenBinTreeMap
785 CDSUNIT_TEST_BronsonAVLTreeMap
786 CDSUNIT_TEST_FeldmanHashMap_fixed
787 CDSUNIT_TEST_FeldmanHashMap_city
788 CDSUNIT_TEST_CuckooMap
789 CPPUNIT_TEST_SUITE_END();
791 // Not implemented yet
792 ////CDSUNIT_DECLARE_StripedMap
793 ////CDSUNIT_DECLARE_RefinableMap
794 ////CDSUNIT_DECLARE_StdMap